作者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/cn.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