c - 找到第一个可用位的最佳方法

Question

给定一个未符号整数数组(每个 4 个八位字节)，找到第一个至少有一个“0”位的元素的最佳方法是什么，它是 LSB 的索引。

例如:其中 n = 9

unsinged int uIntArray[] = {
    0xffffffff,
    0xffffffff,
    0xffffffff,
    0xffffffff,
    0xffffff9f,
    0x00000000,
    0x00000000,
    0x00000000,
    0x00000000,
};

回答:

element's index = 4
bit's index = 4

我只能想到:

int main (void)
{
    bool found_f = false;
    int n = 9;  //our test case value
    unsigned int uIntArray[] = {
        0xffffffff,
        0xffffffff,
        0xffffffff,
        0xffffffff,
        0xffffff8f,
        0x00000000,
        0x00000000,
        0x00000000,
        0x00000000,
    };  

    unsigned int uIntBits [32] = {
        1, 2, 4, 8, 16, 32, 64, 128,
            256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
            65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
            16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648
    };      

    unsigned int idx, jdx;
    int ele_idx = -1; 
    int bit_idx = -1;

    for (idx =0; idx < n; idx ++) {
        if (uIntArray[idx] < UINT_MAX) { /* our candidate */
            for (jdx =0; jdx < 32; jdx ++)  {
                if ((uIntBits[jdx] & uIntArray[idx])) {
                    ele_idx = idx; 
                    bit_idx = jdx;
                    found_f = true;
                    break;
                }   
            }   
        }   
        if(found_f) {
            break;
        }   
    }   
    fprintf (stderr, "\nEleIdx[%d] BitIdx[%d]\n", ele_idx, bit_idx);
    return 0;
}   

有没有更好的方法呢？

Answer 1

x中最低位0的索引是~x中最低位1的索引>。为了找到后者，您只需要计算 ~x 中的尾随零。有很多方法可以做到这一点，请参阅此处 http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear

使用最后一种方法(基于 DeBruijn 序列)，搜索结果如下

static const unsigned MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

for (idx = 0; idx < n; idx ++)
  if (uIntArray[idx] < UINT_MAX)
    break;

if (idx < n) {
  unsigned v = ~uIntArray[idx];
  int bit_idx = MultiplyDeBruijnBitPosition[((v & -v) * 0x077CB531u) >> 27];
  fprintf(stderr, "\nEleIdx[%d] BitIdx[%d]\n", idx, bit_idx);
}