代码之家  ›  专栏  ›  技术社区  ›  SF.

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

  •  8
  • SF.  · 技术社区  · 15 年前

    我有可以被认为是“位数组”的内存区域。它们相当于

    unsigned char arr[256];
    

    但最好把它当作

    bit arr[2048];
    

    我用

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

    但我在代码的许多地方都做了很多工作,通常是在性能关键的部分,我想知道是否有任何更智能、更优化的方法可以做到这一点。

    额外信息:架构:arm9(32位);gcc/linux。物理数据表示不能更改-它是外部提供的或映射的,以供外部使用。

    8 回复  |  直到 15 年前
        1
  •  6
  •   Greg Hewgill    15 年前

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

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

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

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

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

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

        2
  •  7
  •   kennytm    15 年前

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

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

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

        3
  •  3
  •   MSalters    15 年前

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

    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 因为你不想拥有很多这样的功能。

        4
  •  1
  •   sambowry    15 年前

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

        5
  •  1
  •   Thorsten S.    15 年前
    #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慢。你不需要减去, 只需调整设置位程序。

        6
  •  0
  •   Goz    15 年前

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

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

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

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

    所以我有如下内容:

    BitStream< 1 > oneBitBitStream;
    BitStream< 2 > twoBitBitStream;
    
    oneBitBitStream += Bit_One;
    oneBitBitStream += Bit_Zero;
    
    twoBitBitStream += Bit_Three;
    twoBitBitStream += Bit_One;
    

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

        7
  •  0
  •   Max Shawabkeh    15 年前

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

        8
  •  0
  •   Vijay Mathew Chor-ming Lung    15 年前

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