Understanding logic behind Integer.highestOneBit() method implementation

Question

Java Integer class has the static method highestOneBit method which will return a value with a single one-bit, in the position of the highest-order one-bit in the specified value, or zero if the specified value is itself equal to zero.

For example input of int 17 will return 16; As 17 can be represented in binary as 10001 so it will return the furthest bit left which is equal to 16.

And in Integer class it has the following implementation in Java doc.

    public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

I just want to know the logic behind implementing it this way and the logic behind using shift operations . Can any one put some light on it.

Answer 1

This algorithm calculates for a given i whose binary representation is:

0..01XXXXXXX...XXXX

the value

0..011111111...1111

That's what the 5 |= operators do.

Then, in the return statement, it subtracts from it that value shifted right by one bit

0..001111111...1111

to get the result

0..010000000...0000

How does it work:

The highest possible 1 bit the the 32nd (left most) bit. Suppose the input number has 1 in that bit:

1XXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX

You or that value with the value shifted right by 1 (i >> 1) and get

11XXXXXX XXXXXXXX XXXXXXXX XXXXXXXX

Then you or that new value with the value shifted right by 2 (i >> 2) and get

1111XXXX XXXXXXXX XXXXXXXX XXXXXXXX

Then you or that new value with the value shifted right by 4 (i >> 4) and get

11111111 XXXXXXXX XXXXXXXX XXXXXXXX

Then you or that new value with the value shifted right by 8 (i >> 8) and get

11111111 11111111 XXXXXXXX XXXXXXXX

Finally you or that new value with the value shifted right by 16 (i >> 16) and get

11111111 11111111 11111111 11111111

If the highest 1 bit is smaller than the 32nd bit, these operations still turn all the bits to the right of it to 1 and keep the remaining (higher bits) 0.

Answer 2

The i |= statements help to compute a sequence of ones that is the same length as i. For example, for 101011 it computes 111111. I've explained how it works in this answer (I can't retype it right now since I am on mobile).

So basically, once you have the string of ones, subtracting itself shifted right one bit gives the H.O. bit.

111111 - (111111 >>> 1) = 111111 - 011111 = 100000

Answer 3

The first five lines (i |= (i >> x)) will set every bit below the highest 1-bit to 1. Then, the final line will subtract every 1-bit below the highest one, so that only the highest 1-bit will remain.

For simplicity, let's pretend an int was 8 bits. The code would in that case be like this:

public static int highestOneBit(int i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    return i - (i >>> 1);
}

Now, let's say we have the value 128 (10000000). This is what would happen:

// i == 10000000
i |= (i >>  1); // i = 10000000 | 11000000 = 11000000 
i |= (i >>  2); // i = 11000000 | 11110000 = 11110000 
i |= (i >>  4); // i = 11110000 | 11111111 = 11111111
return i - (i >>> 1); // 11111111 - 01111111 = 10000000

The >> is an arithmetic right shift, so it will preserve the signed bit. The last >>> is a logical right shift, which will not preserve the signed bit. It will always insert zeroes on the left side.

Now, let's try with 64 (01000000):

// i == 01000000
i |= (i >>  1); // i = 01000000 | 00100000 = 01100000 
i |= (i >>  2); // i = 01100000 | 00011000 = 01111000 
i |= (i >>  4); // i = 01111000 | 00000111 = 01111111
return i - (i >>> 1); // 01111111 - 00111111 = 01000000