有什么更聪明的方法可以从位数组中提取吗?

对于随机访问单独的位,您建议的宏是尽可能好的(只要您打开编译器中的优化)。

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

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

更新 :因为您可以访问位的范围,所以您可能会从宏中榨取更多的性能。例如,如果需要访问四位,您可能有如下宏:

#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_* 访问器函数。

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

我不这么认为。事实上,许多CPU架构不能单独访问位。

关于C++你有 std::bitset<N> . 但根据编译器的实现和优化,可能没有最高的性能。

顺便说一句,将位数组分组为 uint32_t[32] (或) uint64_t[16] )用于对齐解引用(其中 bitset 已经为你做了)。

以格雷格的解决方案为基础:

template<unsigned int n, unsigned int m> 
inline unsigned long getbits(unsigned long[] bits) {
  const unsigned bitsPerLong = sizeof(unsigned long) * CHAR_BIT
  const unsigned int bitsToGet = m - n;
  BOOST_STATIC_ASSERT(bitsToGet < bitsPerLong);
  const unsigned mask = (1UL << bitsToGet) - 1;
  const size_t index0 = n / bitsPerLong;
  const size_t index1 = m / bitsPerLong;
  // Do the bits to extract straddle a boundary?
  if (index0 == index1) {
    return (bits[index0] >> (n % bitsPerLong)) & mask;
  } else {
    return ((bits[index0] >> (n % bitsPerLong)) + (bits[index1] << (bitsPerLong - (m % bitsPerLong)))) & mask;
  }
}

即使它们没有对齐,也可以得到至少32位。注意这是故意的 inline 因为你不想拥有很多这样的功能。

如果在“arr”中反转位顺序,则可以从宏中消除减法。这是我能说的最好的话,不知道问题的上下文(如何使用位)。

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

可以优化。

1)使用标准int,它通常是最快访问的整数数据类型。 如果不需要便携,可以通过 调整以下代码。

2)

#define GETBIT(x,in)   ((in)[ ((x) >>> 3) ] & 1<<((x) & 7))

mod运算符%比anding慢。你不需要减去, 只需调整设置位程序。

为什么不创建自己的包装类呢?

然后,可以使用+等运算符向“数组”中添加位,并使用[]运算符返回各个位。

您的宏可以通过使用&7而不是%8来改进,但编译器很可能会为您进行优化。

我最近做的正是你在做的,我的流可能包含任何数量的位。

所以我有如下内容:

BitStream< 1 > oneBitBitStream;
BitStream< 2 > twoBitBitStream;

oneBitBitStream += Bit_One;
oneBitBitStream += Bit_Zero;

twoBitBitStream += Bit_Three;
twoBitBitStream += Bit_One;

等等。它提供了一个可读性很好的代码,您可以为它提供一个类似STL的接口来帮助Faimillarity:)

既然问题是用C++来标记的,你有什么理由不能简单地使用这个标准? bitset ?

您可以使用 std::vector<bool> . Vector类模板具有用于bool类型的特殊模板专门化。这个专门化是为了优化空间分配而提供的:在这个模板特化中,每个元素只占用一个比特(它比C++中的最小类型少八倍:char)。