I need a program that returns the number of trailing zeros in the binary rapresentation of a number. I found online a function written in C but I don't understand how it works

This is the function:

```
unsigned tzr(unsigned x)
{
unsigned n; /* number of bits */
n = 0;
if (!(x & 0x0000FFFF)) { n += 16; x >>= 16; }
if (!(x & 0x000000FF)) { n += 8; x >>= 8; }
if (!(x & 0x0000000F)) { n += 4; x >>= 4; }
if (!(x & 0x00000003)) { n += 2; x >>= 2; }
n += (x & 1) ^ 1; // anyway what does this do ?
return n;
}
```

Now I've really tried to understand how this works but I don't get it. I really need someone who could explain it to me, I find this code very complicated.

And about those hexadecimal constants, these are their values:

`0x0000FFFF`

= 65535

`0x000000FF`

= 255

`0x0000000F`

= 15

`0x00000003`

= 3

Now, why the program uses those values and makes a bitwise AND with the number?

Then I know that if you want to handle big numbers you must

use a `while`

instead of the first `if`

statement, like this:

```
while (!(x & 0x0000FFFF)) { bits += 16; x >>= 16; } // why should I need this ?
```

But I don't know why ! What's the difference about using a `while`

instead of an `if`

in this case?

The hexadecimal constants are AND'ed with the value to check whether the last [number] of digits is zero.`0x0000FFFF`

is a number with 16 ones in binary. If the value AND'ed with `0x0000FFFF`

is equal to 0, you know that the last 16 digits are zeroes (the `if`

s check for the reverse of that statement). Going further `0x000000FF`

is a number with 8 ones in binary. The next check is for the last 8 digits, next for 4 digits and the last one for 2 digits as `0x00000003`

is `11`

in binary. After the checks the numbers are shifted to check whether further digits are also zero. This way we can check for any number of trailing zeroes as the values are powers of 2 and adding them works exactly like working with binary.

Last statement checks for the last digit after all the previous shifting is done - AND with 1 and checking if it's 0 or 1 with a XOR(`^`

).

This program checks numbers with 32 bits. You can change the first `if`

to a `while`

to check larger, e.g. 64-bit, numbers. Another way is to check with `0xFFFFFFFF`

and then shift 32 bits at once.

The line `n += (x & 1) ^ 1`

checks the least significant bit (LSB) of the current state of x. If the LSB is a 1 then (x & 1) yeilds 1 which is then XORed (the caret symbol '^' means to XOR two values) with 1 to give 0 (1 ^ 1 == 0). When x has a 0 in the LSB and is XORed with 1 it yeilds 1 (0 ^ 1 == 1).

answered on Stack Overflow Jul 23, 2017 by amisam

`!(x&0x0000FFFF)`

will be true only when the last 16 bits of `x`

are all 0's.
The `&`

is a bitwise and, and `0x0000FFFFF`

is the number ending in 16 1's.
So the result of the and is 0 iff all 16 trailing bits are 0 (and so FALSE and `1`

reverses the truth value) because if there is at least one 1 among the last 16, the and with the corresponding 1 in the constant will be 1. So then the and is not 0 (so TRUE and `!`

reverses the truth value).

So the code says: if the last 16 bits are 1, add 16 to n and throw the last 16 bits away (that is what `x >>= 16`

does).

The next line says in a similar way:
if the last 8 bits of the (possibly shortened `x`

) are 0 ,add 8 to n and throw the rightmost 8 bits away, and so on for 4 and 2 bits as well

The last line adds 1 if the rightmost bit (`x&1`

) is 0, otherwise 0 (`1^1 = 0`

).

So say if the righmost 15 bits are 0, the first `if`

will be false , n remains 0.

The second will be true, as we have more than 8. Tne new x will have 7 0-bits,
and n=8.

The third will also be true (we have still 4 or more), so the new x has 3 0-bits after the shift and n=12.

The fourth will also be true (2 or more 0's) so the new x has 1 0-bit and n=14.

The final statement adds 1, so get n=15.

Because we use decreasing powers of 2 we don't need a loop. We get all possible n values this way (except 32, for input `x=0`

, a fully correct function should maybe check for that and early abort.

answered on Stack Overflow Jul 23, 2017 by Henno Brandsma

`n += (x & 1) ^ 1; // anyway what does this do ?`

This checks the right-most bit. Either it is set or NOT set.

If it is set, then there is NOT another 0 to add onto the running total of trailing zeros, so n+=0.

If it is NOT set, then there is another 0 to add onto the running total of trailing zeros, so n+=1.

Also, your example does NOT compile, it is missing two ; as follows:

```
unsigned tzr(unsigned x)
{
unsigned n; /* number of bits */
n = 0;
if (!(x & 0x0000FFFF)) { n += 16; x >>= 16; }
if (!(x & 0x000000FF)) { n += 8; x >>= 8; }
if (!(x & 0x0000000F)) { n += 4; x >>= 4 } // won't compile due to missing ;
if (!(x & 0x00000003)) { n += 2; x >>= 2 } // won't compile due to missing ;
n += (x & 1) ^ 1; // anyway what does this do ?
return n;
}
```

Also, you can always try printing out data, for example, every power of 2 has multiple trailing zeros, but only odd amounts of trailing zeros are incremented by an additional 1 from `n += (x & 1) ^ 1;`

...

```
cout << tzr(9) << endl << endl; // 1001 (not a power of two )
cout << tzr(8) << endl << endl; // 1000 (8>>2 & 1)^1==1
cout << tzr(4) << endl << endl; // 0100 (4>>2 & 1)^1==0
cout << tzr(2) << endl << endl; // 0010 ( 2 & 1)^1==1
cout << tzr(1) << endl << endl; // 0001 ( 1 & 1)^1==0
```

tzr(9) == 0 ==> 0 + (9 & 1) ^ 1 == 0 + 0

tzr(8) == 3 ==> 2 + (8>>2 & 1) ^ 1 == 2 + 1

tzr(4) == 2 ==> 2 + (4>>2 & 1) ^ 1 == 2 + 0

tzr(2) == 1 ==> 0 + (2 & 1) ^ 1 == 0 + 1

tzr(1) == 0 ==> 0 + (1 & 1) ^ 1 == 0 + 0

Program ended with exit code: 0

answered on Stack Overflow Jul 23, 2017 by claytonjwong

You say, "I need a program that returns the number of trailing zeros in the binary rapresentation of a number." But does it have to be the program you found? Here's an alternative solution that implements tzr() in exactly one line of code,

```
#include <stdio.h>
#include <stdlib.h>
int tzr(int n) { /* --- every time n is even, add 1 and check n/2 --- */
return ( (n/2)*2 == n? 1+tzr(n/2) : 0 ); }
int main ( int argc, char *argv[] ) { /* --- test driver --- */
int n = (argc>1? atoi(argv[1]) : 1000);
printf("tzr(%d) = %d\n", n,tzr(n)); }
```

Is that any easier to understand?

(P.S. You could use bit masks and shifts instead of my divides and multiplies. That might be a little more efficient, but I thought my way might be a little more straightforward to read.)

User contributions licensed under CC BY-SA 3.0