作者handofn0xus (你真是糟糕的小焰)
看板C_and_CPP
標題[問題] 如何將整個陣列的資料進行位移？
時間Tue Feb 7 11:27:24 2023
最近遇到需要把Bitmap中的資料進行位移的情況
Bitmap是以char*的形式進行儲存
今天我想做的事是
以下列為例：
char bitmap[]={0xA5,0x05,0x05}
1. 我今天想從bitmap[0]的第五個位元進行右移2
2. 同時bitmap[2]的資料不會因為右移而消失 而是到bitmap[3]
也就是結果會變成
{0xA1,0x41,0x41,0x40}
2.可以透過realloc解決 所以不算是問題
但是1.我就不知道該怎麼下手了 我實在不知道怎麼把不同元素的資料位移到下個元素去
而資料不會消失
想請教各位先進 要怎麼樣才能達到我想要的效果呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.130.45.59 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1675740450.A.E41.html
※ 編輯: handofn0xus (220.130.45.59 臺灣), 02/07/2023 11:28:29
1F：→ terter: 一時想到比較笨的方法是，從最後解。假設原陣列A,新陣列B02/07 11:59
2F：→ terter: B[3]=A[2]<<6, B[2]=A[1}<<6+A[2}>>202/07 12:00
我剛剛發文後也想到這個方法
目前也是先用這樣的方法去寫 但不知道有沒有更簡單的方式能達成目標 尤其是要應付大量
資料的情況
3F：→ terter: 想了一下，好像用型別轉換去作比較快，一次可以處理多個 02/07 12:07
4F：→ terter: 譬如說用uint64這種 02/07 12:08
謝謝 這樣確實能提升一些速度
不過還是想問問看 假設我的bitmap有e.g. 超過1000個index
這樣即使用uint64還是會需要重複好幾遍
真的沒有辦法是可以直接對整個陣列所有位元進行移動的方法嗎？
5F：→ Lipraxde: 有更完整的使用情境嗎？ 02/07 15:27
6F：推 lwecloud: tmp = bitmap[i] & 0xFC; 02/07 15:28
7F：→ lwecloud: bitmap[i] = (bitmap[i] >> 6) & 0x3F; 02/07 15:29
8F：→ lwecloud: bitmap[i] |= (remain << 6) & 0xC0; 02/07 15:30
9F：→ lwecloud: remain = tmp; 02/07 15:30
10F：→ lwecloud: 這樣呢? (用推文好難打 囧) 02/07 15:31
11F：→ lwecloud: 第一行就錯了 tmp = bitmap[i] & 0x3; 才對... 02/07 15:32
12F：→ lwecloud: 陽春做法，搞不好有些library可以直接做到 02/07 15:42
能大概了解你想表達的意思 感謝
13F：→ leolarrel: terter的型別轉換法目前看起來最快最簡潔 02/07 17:37
14F：推 don323: 類似二樓的寫法就是最快的，客製化各種運算 02/08 08:13
※ 編輯: handofn0xus (220.130.45.59 臺灣), 02/08/2023 15:55:39
15F：推 johnjohnlin: char不小心shift太多會UB，最好先轉unsigned 02/08 21:47
16F：→ johnjohnlin: 戳到MSB變1會是UB 02/08 21:48
17F：→ yesiah: stackoverflow 有類似的討論 02/09 11:50
19F：→ yesiah: 看了一下有兩個方向 02/09 11:50
20F：→ yesiah: 一個是想辦法用SIMD instructions，另一個是一邊寫loop一 02/09 11:50
21F：→ yesiah: 邊看assembly有沒有良好vectorize 02/09 11:50
22F：→ yesiah: 第二個方法可能要加__restrict讓compiler知道src跟dst不重 02/09 11:50
23F：→ yesiah: 疊，所以他可以做更多最佳化 02/09 11:50
24F：→ longlongint: 如果要平行化 又不用省空間的話 掛一層f(idx) 04/09 23:03
25F：→ longlongint: 就可以分段copy了 04/09 23:04