How does Integer.numberOfTrailingZero(int i) work?

Question

This question is related to but it is different in understanding how the code actually works. More precisely, I do not understand how numberOfTrailingZeros(int i) in java 8 here compute the final result. The code is as follows

   public static int numberOfTrailingZeros(int i) {
    // HD, Figure 5-14
    int y;
    if (i == 0) return 32;
    int n = 31;
    y = i <<16; if (y != 0) { n = n -16; i = y; }
    y = i << 8; if (y != 0) { n = n - 8; i = y; }
    y = i << 4; if (y != 0) { n = n - 4; i = y; }
    y = i << 2; if (y != 0) { n = n - 2; i = y; }
    return n - ((i << 1) >>> 31);
    }

Now I understand the purpose of the shift operations from 16 to 2, but won't n have already the number of trailing zeros by the last shift operation:

y = i << 2; if (y != 0) { n = n - 2; i = y; }. 

That is I do not understand the purpose of this particular line

n - ((i << 1) >>> 31); 

why do we need that when n has already the right value?

Can anyone give a detailed example of what is going on?

Thanks!

Answer 1

I will try to explain the algorithm. It is a bit optimized, but I'll start with a (hopefully) more simplified approach.

It is used to determine the number of trailing zero bits of a 32 bit number, that is, how many zeros are on the right side (assuming most significant bit on left). The main idea is to divide the field in two half: if the right one is all zero we add the number of bits in the right half to the result and continue examining the left one (again dividing it); if the right one is not all zero, we can ignore the left one and continue examining the right one (adding nothing to the result).

Example: 0000 0000 0000 0010 0000 0000 0000 0000 (0x0002 0000)

first step (not java code, all numbers base 2, result is decimal):

i = 0000 0000 0000 0010   0000 0000 0000 0000
left  = 0000 0000 0000 0010
right = 0000 0000 0000 0000
result = 0

since right is zero, we add 16 (actual number of bits in right part) to the result and continue examining the left part

second step:

i = 0000 0000 0000 0010   // left from previous
left =  0000 0000
right = 0000 0010
result = 16

now right is not zero, so we add nothing to result and continue with right part

third step:

i = 0000 0010    // right from previous
left =  0000
right = 0010
result = 16

right is not zero, nothing added to result, continue with right part

4th step:

i = 0010    // right from previous
left =  00
right = 10
result = 16

5th step:

i = 10     // right from previous
left = 1
right = 0
result = 16

now right is zero, so we add 1 (number of bits in right part) and there is nothing else to divide (that is the return line off original code)

result = 17

Optimizations: instead of having the left and the right part, the algorithm only examines the left left x-most bits of the number and just shift the right part into the left if the right one is not zero, example for first step:

y = i << 16; if (y != 0) { ... i = y;}

and, to avoid having an else part (I think), it starts the result with 31 (sum of all part lengths 1+2+4+8+16) and subtracts the bit count if the right side (after shifting the now left one) is not zero. Again for the first step:

y = i << 16; if (y != 0) { n = n - 16; ....} 

Second optimization, last step, instead of

y = i << 1; if (y != 0) { n = n - 1; /* i = y not needed since we are done*/ }
return n;

it does just

return n - ((i << 1) >>> 31);  

here ((i << 1) >>>31) is shifting the second bit (second leftmost, second highest bit) of i to leftmost position (eliminating the first bit) and then shifting it to rightmost position, that is, resulting in 0 if the second bit is zero, 1 otherwise. Which is then subtracted from the result (to undo the sum 31 from the beginning).

The first (leftmost) bit need not be directly examined. It only matters if all other bits are zero, that is, the number is 0, checked at the very beginning (if (i == 0) return 32;) or it is -1 in which case the initial value of result is returned: 31.