任何更聪明的方式，从位阵列提取？ [英] Any smarter way to extract from array of bits?

问题描述

我有可能被认为是比特数组的内存区域。它们相当于

I have areas of memory that could be considered "array of bits". They are equivalent to

unsigned char arr[256];

不过，这将是更好的思想

But it would be better thought of as

bit arr[2048];

我访问单独的位从它

I'm accessing separate bits from it with

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

但我做了很多在code的许多地方，往往在性能关键的部分，我不知道是否有任何更聪明，更优化的方法来做到这一点。

but I do it a lot in many places of the code, often in performance-critical sections and I wonder if there are any smarter, more optimal methods to do it.

额外的信息：架构：ARM9（32位）;海合会/ Linux操作系统。物理数据重新presentation不能改变 - 它是由外部提供或映射外用

extra info: Architecture: ARM9 (32 bit); gcc/Linux. The physical data representation can't be changed - it is externally provided or mapped for external use.

推荐答案

有关随机访问单个位，你建议宏是不如你会得到（只要你在你的编译器打开的优化）。

For randomly accessing individual bits, the macro you've suggested is as good as you're going to get (as long as you turn on optimisations in your compiler).

如果有一个在所有您所访问的任何位模式，那么你可以做的更好。例如，如果你经常访问的对的位，那么你可以通过提供一个方法来获得两个位，而不是一看到一些改善，即使你并不总是最终使用两个位。

If there is any pattern at all to the bits you're accessing, then you may be able to do better. For example, if you often access pairs of bits, then you may see some improvement by providing a method to get two bits instead of one, even if you don't always end up using both bits.

对于任何优化问题，你需要非常熟悉您的code的行为，特别是其访问模式的位阵列中，使性能有重大改善。

As with any optimisation problem, you will need to be very familiar with the behaviour of your code, in particular its access patterns in your bit array, to make a meaningful improvement in performance.

更新：既然你访问位的范围，你也许可以挤一些表现出来的宏。例如，如果您需要访问四位你可能有这样的宏：

Update: Since you access ranges of bits, you can probably squeeze some more performance out of your macros. For example, if you need to access four bits you might have macros like this:

#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等夹出四位（为了减少无意义的括号内的扩散，你可能需要使用内联函数的上方。）那么也许定义一个内联像功能：

These macros would clip out four bits from each bit position 0, 1, 2, etc. (To cut down on the proliferation of pointless parentheses, you might want to use inline functions for the above.) Then perhaps define an inline function like:

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
    }
}

由于这是很多繁琐的样板code，特别是如果你有多个不同的宽度，你可能需要编写一个程序来生成所有的 GETBIT _ * 存取功能。

（我注意到，你的字节位存储在从我上面写的顺序相反。应用适当的变换，以配合您的结构，如果你需要。）

(I notice that the bits in your bytes are stored in the reverse order from what I've written above. Apply an appropriate transformation to match your structure if you need to.)

这篇关于任何更聪明的方式，从位阵列提取？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！