c++ - C/C++ 中对位数组的两种操作

Question

// b: uint32_t array of size n    => 32*n bits
// The bit index, i, is in the range 0 <= i < 32 * n
// The bit in b at bit index 0 is always 0!

unsigned idx_of_first_zero_bit_before_or_at (uint32_t *b, unsigned n, unsigned i) {
    // Returns a bit index, k, such that k <= i and k is the largest bit index
    // for which bit k in b is 0.
}

// As above, value == 0 or 1
void set_bit (uint32_t *b, unsigned n, unsigned i, unsigned value) {
    // Sets bit at bit index i to value.
    // It could be something like (untested):
    if (value)
        b[i >> 5] |=   (1 << (i&31));
    else
        b[i >> 5] &= (~(1 << (i&31)));
}

我正在寻找最有效但仍然可移植(跨不同目标，但只使用 g++ 编译器)的方法来实现这些功能(尤其是第一个)。位的存储顺序(大端、小端或其他)无关紧要。

简单的实现(未经测试):

uint32_t get_bit (uint32_t *b, unsigned n, unsigned i) {
    return b[i >> 5] & (1 << (i&31));
}

unsigned idx_of_first_zero_bit_before_or_at (uint32_t *b, unsigned n, unsigned i) {
    while (get_bit (b, n, i)) 
        i--;
    return i;
}

跳过所有 1 个元素:

unsigned idx_of_first_zero_bit_before_or_at (uint32_t *b, unsigned n, unsigned i) {
    for (unsigned k = i >> 5; ~(b[k]) == 0; i = (--k << 5) + 31);
    while (get_bit (b, n, i)) 
        i--;
    return i;
}

Answer 1

根据您有多少可用存储空间，您可以采用查找表方法。例如，如果您可以花费 256 个字节，那么以下函数会为单个 uint32_t 执行此操作:

static const int table[256] = { 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
    3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 0, 0,
};


int func(uint32_t b, int i)
{
    b = (b << (31-i));

    if ((b & 0xFFFF0000) != 0xFFFF0000)
    {
        return ((b & 0xFF000000) != 0xFF000000)
             ? table[(b >> 24) & 0xFF] + 24 - (31-i)
             : table[(b >> 16) & 0xFF] + 16 - (31-i);
    }
    else
    {
        return ((b & 0xFF00) != 0xFF00)
             ? table[(b >> 8) & 0xFF] + 8 - (31-i)
             : table[(b >> 0) & 0xFF] + 0 - (31-i);
    }
}

我相信这可以进一步优化。例如，肯定有办法消除昂贵的条件分支；您可以使用 bool 条件计算为 1 或 0 的事实，并将它们用作被乘数。

如果您有 64kB 可用，那么您一次对 16 位 block 执行此操作，依此类推。当然，在大表上进行随机访问可能会发挥缓存作用，因此您需要进行试验和分析。