cbinarybit-manipulation

Finding trailing 0s in a binary number


How to find number of trailing zeros in a binary number?

I took the K&R bitcount example for finding the number of ones in a binary number and I modified it to find the trailing number of trailing zeros:

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

I would like to have this method reviewed.


Solution

  • From https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel, here's a way to compute the count in parallel for better efficiency:

    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;