两个操作/ 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))); 
} 

我正在寻找最有效的，但仍然可移植的（在不同的目标，但仅使用了克++编译器）的方式来实现这些功能（尤其是第一一）。位（大，小端或其他）的存储顺序无关紧要。

天真实现（未经测试）：

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

我敢肯定，这可以进一步优化。例如，有一些方法可以消除昂贵的条件分支;您可以使用布尔条件评估为1或0的事实，并将它们用作被乘数。

如果您有64kB可用，那么您一次在16位块上执行此操作，依此类推。当然，在大型桌面上随机访问可能会带来缓存效果，因此您需要进行实验和配置文件。

Answer 2

通常我会尝试避免“随机”分支。例如，我们可以采用奥利查尔斯沃斯提出的解决方案，并摆脱if s。

它解决了LUT的大部分计算，但最后一部分仍然需要分支。引入额外的LUT来对付它：

unsigned index2 = table[ b  & 0xFF]  | // Values 0..7, so we use 3 bits 
       (table[(b >> 8) & 0xFF] << 3) | // Next 3 bits.. 
       (table[(b >> 16) & 0xFF] << 6) | 
       (table[(b >> 24) & 0xFF] << 9); 

现在，我们在index2 12位的值，我们可以转化为有意义的值用单表查询：

return table2[index2]; // char[4096] array with precomputed values. 

此外，通过首先使用16位查找表，我们将最终得到两个16位查找和一个8位查找。

Answer 3

您可以使用二进制搜索到一个UINT32内找到一个零位。您也可以用查找表替换最后几个步骤，以平衡LUT的内存占用与指令。首先，一个控制流程的解决方案：

unsigned idx_of_first_zero_bit(uint32_t n) { 
    int idx = 0; 
    if (n == 0xffffffff) return 32; // Not found; presumably the common case 

    // Binary search 
    if (n & 0xffff == 0xffff) { 
    n >>= 16; 
    idx += 16; 
    } 
    if (n & 0xff == 0xff) { 
    n >>= 8; 
    idx += 8; 
    } 
    if (n & 0xf == 0xf) { 
    n >>= 4; 
    idx += 4; 
    } 
    if (n & 0x3 == 0x3) { 
    n >>= 2; 
    idx += 2; 
    } 
    if (n & 0x1 == 0x1) { 
    n >>= 1; 
    idx += 1; 
    } 
    return idx; 
} 

为避免分支误预测，可以使用按位运算来实现条件更新。

 
int shift; 

// First step 
shift = ((n & 0xffff == 0xffff) << 4); // shift = (n & 0xffff == 0xffff) ? 16 : 0 
n >>= shift; 
idx += shift; 

// Next step 
shift = ((n & 0xff == 0xff) << 3); // shift = (n & 0xff == 0xff) ? 8 : 0 
n >>= shift; 
idx += shift;