从比特数组中提取的更聪明的方法是什么？

Question

我有一些内存可以被认为是"位数组".他们相当于

unsigned char arr[256];

但它最好被认为是

bit arr[2048];

我正在从中访问单独的位

#define GETBIT(x,in)   ((in)[ ((x)/8) ] & 1<<(7-((x)%8)))

但我在代码的许多地方做了很多,通常是在性能关键的部分,我想知道是否有更聪明,更优化的方法来做到这一点.

额外信息:架构:ARM9(32位); GCC/Linux操作系统.无法更改物理数据表示 - 从外部提供或映射以供外部使用.

Answer 1

我不这么认为.实际上,许多CPU架构不会单独访问位.

在C++上你有std::bitset<N>.但可能没有最高性能,具体取决于编译器的实现和优化.

顺便说一下,最好将位数组分组为uint32_t[32](或uint64_t[16])用于对齐解除引用(这bitset已经为你做了这个).

Answer 2

对于随机访问单个位,您建议的宏与您将获得的一样好(只要您在编译器中启用优化).

如果您正在访问的位有任何模式,那么您可以做得更好.例如,如果您经常访问位对,那么通过提供一个获取两位而不是一位的方法,您可能会看到一些改进,即使您并不总是最终使用这两位.

与任何优化问题一样,您需要非常熟悉代码的行为,特别是其位数组中的访问模式,以便在性能方面做出有意义的改进.

更新:由于您访问位的范围,您可以从宏中挤出更多性能.例如,如果您需要访问四位,您可能有这样的宏:

#define GETBITS_0_4(x,in) (((in)[(x)/8] & 0x0f))
#define GETBITS_1_4(x,in) (((in)[(x)/8] & 0x1e) >> 1)
#define GETBITS_2_4(x,in) (((in)[(x)/8] & 0x3c) >> 2)
#define GETBITS_3_4(x,in) (((in)[(x)/8] & 0x78) >> 3)
#define GETBITS_4_4(x,in) (((in)[(x)/8] & 0xf0) >> 4)
#define GETBITS_5_4(x,in) ((((in)[(x)/8] & 0xe0) >> 5) | (((in)[(x)/8+1] & 0x01)) << 3)
#define GETBITS_6_4(x,in) ((((in)[(x)/8] & 0xc0) >> 6) | (((in)[(x)/8+1] & 0x03)) << 2)
#define GETBITS_7_4(x,in) ((((in)[(x)/8] & 0x80) >> 7) | (((in)[(x)/8+1] & 0x07)) << 1)
// ...etc

这些宏将从每个位位置0,1,2等中删除四位.(为了减少无意义括号的扩散,您可能希望使用内联函数来实现上述.)然后可能定义内联函数,如:

inline int GETBITS_4(int x, unsigned char *in) {
    switch (x % 8) {
        case 0: return GETBITS_0_4(x,in);
        case 1: return GETBITS_1_4(x,in);
        case 2: return GETBITS_2_4(x,in);
        // ...etc
    }
}

由于这是一个繁琐的样板代码,特别是如果你有多个不同的宽度,你可能想编写一个程序来生成所有的GETBIT_*访问器函数.

(我注意到你的字节中的位以与我上面写的相反的顺序存储.如果需要,应用适当的转换来匹配你的结构.)