Trailing zeros - C
I need a program that returns the number of trailing zeros in the binary representation of a number. I found a function online 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 was really trying to figure out how it works, but I don't get it. I really need someone who can explain this to me, I find this code very difficult.
And about those hexadecimal constants, these are their meanings:
0x0000FFFF
= 65535 0x000000FF
= 255 0x0000000F
= 15 0x00000003
= 3
Now why does the program use these values ββand do a bitwise AND with a number?
Then I know that if you want to handle large numbers you should use while
instead of the first operator if
, for example:
while (!(x & 0x0000FFFF)) { bits += 16; x >>= 16; } // why should I need this ?
But I do not know why! What's the difference in using while
instead if
in this case?
source to share
Hexadecimal constants are AND to check if the last [number] digits are equal. 0x0000FFFF
- number with 16 in binary format. If the value of AND_ed c 0x0000FFFF
is 0, you know the last 16 digits are zeros (check if
for the inverse of this operator). Further 0x000000FF
- the number with 8 in binary format. The next check is for the last 8 digits, the next is for 4 digits, and the second is for 2 digits as 0x00000003
- 11
in binary. After the checks, the numbers are shifted to check if the digits are still equal. This way, we can check for any number of trailing zeros, since the values ββhave values ββof 2 and adding them works exactly the same as working with binary.
The last instruction checks the last digit after the previous offset is AND with 1 and checks if it is 0 or 1 with XOR ( ^
).
This program checks numbers with 32 bits. You can change the first one if
to while
to check more, for example. 64-bit numbers. Another way is to check with 0xFFFFFFFF
and then shift 32 bits at once.
source to share
The string n += (x & 1) ^ 1
checks the least significant bit (LSB) of the current state x. If LSB is 1, then (x and 1) yeilds 1, which is then XORed (the caret character "^" means XOR the two values) with 1 to give 0 (1 ^ 1 == 0). When x has 0 in LSB and XORed with 1, it is yeilds 1 (0 ^ 1 == 1).
source to share
!(x&0x0000FFFF)
will be true only if the last 16 bits x
- all 0s
&
are bitwise, and 0x0000FFFFF
- a number ending in 16 1. Thus, the result is 0 if all 16 trailing bits are 0 (and therefore FALSE and 1
change the value of true), because if in the last 16 there is at least one 1, then with the corresponding 1 in the constant there will be 1. So, then it is not equal to 0 (therefore TRUE and !
change the value of true).
So the code says: if the last 16 bits are 1, add 16 to n and throw away the last 16 bits (which is what it does x >>= 16
).
The next line says in a similar way: if the last 8 bits of the (possibly abbreviated x
) are 0, add 8 to n and discard the rightmost 8 bits, etc. 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
).
Let's say if the first 15 bits are 0, the first if
will be false, n will remain 0. The
second will be true, since we have more than 8. The new x will have 7 0 bits, and n = 8. The third will also be true (we have 4 more 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 0s), so the new x has 1 0-bits and n = 14.
The final statement adds 1, so we get n = 15.
Since we're using decreasing powers of 2, we don't need a loop. We get all possible n values ββin this way (except 32, for input x=0
, a perfectly correct function should, perhaps, check this and abort early.
source to share
n += (x & 1) ^ 1; // anyway what does this do ?
This checks the rightmost bit. Either it is installed or NOT installed.
If set, then NOT add another 0 to add trailing zeros, so n + = 0.
If it is NOT set, another 0 is added to add trailing zeros to the current total, so n + = 1.
Also, your example does NOT compile, it is missing two; in the following way:
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 to print the data, for example, each cardinality of 2 has multiple trailing zeros, but only odd numbers of trailing zeros increase by an extra 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 and 1) ^ 1 == 0 + 0
tzr (8) == 3 ==> 2 + (8 β 2 and 1) ^ 1 == 2 + 1
tzr (4) == 2 ==> 2 + (4 -> 2 and 1) ^ 1 == 2 + 0
tzr (2) == 1 ==> 0 + (2 and 1) ^ 1 == 0 + 1
tzr (1) == 0 ==> 0 + (1 and 1) ^ 1 == 0 + 0
Program terminated with exit code: 0
source to share
You say, "I want a program that returns the number of trailing zeros in the binary representation of a number." But should there be a program you found? Here's an alternative solution implementing tzr () in just 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 it easier to understand?
(PS You can use bit masks and shifts instead of my divisions and multiplications. This might be a little more efficient, but I thought my way might be a little easier to read.)
source to share