Finding trailing 0s in binary number

Question

How to find the number of trailing 0s in a binary number? Based on the example of the & R bitcount bit for finding 1s in a binary number, I changed it a bit to find trailing 0s.

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

I would like to review this method.

Answer 1

Here you can calculate the score in parallel to increase 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; 

Answer 2

In G86 on the X86 platform you can use __builtin_ctz(no) In Microsoft compilers for X86 you can use _BitScanForward

Both of them emit the bsf command.

Answer 3

Another approach (I am surprised that it is not mentioned here) would be to build a table of 256 integers, where each element in the array is the least significant 1 bit for this index. Then for each byte in integers you look at the table.

Something like this (I did not find the time to set it up, this is just to illustrate the illustration):

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

The idea with some tabular approaches to this problem is that the if cost you something in terms of branch prediction, so you should try to reduce them. It also reduces the number of bit shifts. Your approach uses an if and a shift by bit, and one byte each. (I hope the optimizer can expand the for loop and does not give a comparison / jump for it.) Some other answers have fewer if than this, but the approach to the table is simple and straightforward. Of course, you should be guided by actual measurements to find out if that matters.

Answer 4

Must be:

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

or even

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

or even (yay!)

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

or...

Ah, regardless, there are 100500 million methods of this . Use whatever you need or like.

Answer 5

I think your method works (although you can use unsigned int ). You check the last digit every time, and if it is zero, you drop it by incrementing the number of trailing zero bits.

I think for trailing zeros you don't need a loop.

Consider the following:

• What happens to the number (in binary representation, of course) if you subtract 1? What numbers are changing that remain unchanged?
• How could you combine the source number and the decremented version so that only bits representing trailing zeros remain?

If you apply the above steps correctly, you can simply find the most significant bit set in the O (lg n) steps (see here if you are “Wondering how to do this”.

Answer 6

I have a fast and efficient :

 int bitcount(unsigned __int64 value) { if (!value) return SOME_DEFAULT_VALUE; value &= -value; unsigned int lsb = (unsigned) value | (unsigned) (value >> 32); return (int)(((((((((((unsigned) (value >> 32) != 0) * 2) + ((lsb & 0xffff0000) != 0)) * 2) + ((lsb & 0xff00ff00) != 0)) * 2) + ((lsb & 0xf0f0f0f0) != 0)) * 2) + ((lsb & 0xcccccccc) != 0)) * 2) + ((lsb & 0xaaaaaaaa) != 0); } 

but be careful, as you see there are 2 problems:

• This function is defined for 64-bit integers. (you can use it with casting)
• For a value of 0 you must define a default value. (e.g. 0 or -1 )

I think that these problems are bearable with some caution.

Answer 7

We can easily get it using bit operations, we do not need to go through all the bits. Pseudocode:

 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 } 

Answer 8

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

Explanation:

x and -x returns the number of the most suitable bit with 1.

eg. 6 → "0000.0110", (6 and -6) → "0000.0010"

You can subtract this with two additions: x = "a1b", where b represents all trailing zeros. then

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

So

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

you can get the number of trailing zeros by simply doing log2.