在二进制数中查找尾随0

Question

如何在二进制数中找到尾随0的数量？基于K&R bitcount在二进制数中找到1的示例我修改了一下以找到尾随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) 在X86平台的Microsoft编译器上，可以使用_BitScanForward

它们都发出bsf指令