查找二进制数中的尾随 0

Question

如何查找二进制数中尾随 0 的数量？基于在二进制数中查找 1 的 K&R bitcount 示例，我对其进行了一些修改以查找尾随 0。

int bitcount(unsigned x)
{
  int b;
  for(b=0;x!=0;x>>=1)
      {
        if(x&01)
          break;
        else
          b++;
      }

我想回顾一下这个方法。

Answer 1

这是一种并行计算计数以提高效率的方法：

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

Answer 2

在 X86 平台上的 GCC 上您可以使用

__builtin_ctz(no)

在 Microsoft X86 编译器上，您可以使用

_BitScanForward

它们都发出 bsf 指令

Answer 3

另一种方法（我很惊讶这里没有提到）是构建一个包含 256 个整数的表，其中数组中的每个元素都是该索引的最低 1 位。然后，对于整数中的每个字节，您在表中查找。

类似这样的东西（我没有花任何时间来调整它，这只是为了粗略地说明这个想法）：

int bitcount(unsigned x)
{
   static const unsigned char table[256] = { /* TODO: populate with constants */ };

   for (int i=0; i<sizeof(x); ++i, x >>= 8)
   {
      unsigned char r = table[x & 0xff];

      if (r)
         return r + i*8;    // Found a 1...
   }

   // All zeroes...
   return sizeof(x)*8;
}

一些表驱动方法解决此类问题的想法是，

if

语句会在分支预测方面花费一些成本，因此您应该致力于减少它们。它还减少了位移的数量。您的方法执行

if

语句和每一位移位，而这个方法每字节执行一次。 （希望优化器可以展开 for 循环，而不是为此发出比较/跳转。）其他一些答案的

if

语句甚至比这更少，但表方法简单且易于理解。当然，您应该以实际测量为指导，看看这是否重要。

Answer 4

int countTrailZero(unsigned x) {
    if (x == 0) return DEFAULT_VALUE_YOU_NEED;
    return log2 (x & -x);  
}

说明：

x & -x 返回设置为 1 的最右边位的数量。

例如6 -> “0000,0110”, (6 & -6) -> “0000,0010”

您可以将其减去两个补数： x = "a1b"，其中 b 代表所有尾随零。 然后

-x = !(x) + 1 = !(a1b) + 1 = (!a)0(!b) + 1 = (!a)0(1...1) + 1 = (!a)1(0...0) = (!a)1b 

所以

x & (-x) = (a1b) & (!a)1b = (0...0)1(0...0)

只需执行 log2 即可获得尾随零的数量。

Answer 5

我认为你的方法有效（尽管你可能想使用

unsigned int

）。您每次都会检查最后一位数字，如果它为零，则将其丢弃并增加尾随零位的数量。

我认为对于尾随零，你不需要循环。

考虑以下因素：

• 如果减去 1，数字（当然是二进制表示形式）会发生什么？哪些数字发生变化，哪些保持不变？
• 如何将原始数字和递减版本组合起来，以便只留下表示尾随零的位？

如果正确应用上述步骤，您只需在 O(lg n) 步骤中找到设置的最高位（如果您对如何做感兴趣，请查看 here）。

Answer 6

应该是：

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7; x>>=1)
  {
    if(x&1)
      break;
    else
      b++;
  }
  return b;
}

甚至

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7 && !(x&1); x>>=1) b++;
  return b;
}

甚至（耶！）

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7 && !(x&1); b++) x>>=1;
  return b;
}

或...

啊，无论如何，有 1005 亿种方法可以做到这一点。使用您需要或喜欢的任何东西。

Answer 7

我们可以通过位运算轻松得到它，我们不需要遍历所有的位。伪代码：

int bitcount(unsigned x) {
    int xor = x ^ (x-1); // this will have (1 + #trailing 0s) trailing 1s
    return log(i & xor); // i & xor will have only one bit 1 and its log should give the exact number of zeroes
}