Why this bit manipulation return this result?

Question

there is a java code:

private static final int tableSizeFor(int c) {
    int n = c - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : n + 1;
}

the result is: min(times of 2 and >=c)

for example, if c is 5,the result will be 8,if c is 16,the result will be 16.

I have calculated as the algorithm shows but I don't know how to understand this algorithm,anyone can explain this clearly,thanks.

http://stackoverflow.com/q/1322510/995714 http://stackoverflow.com/q/4398711/995714 — phuclv, Jan 06 '16 at 07:08

score 0 · Accepted Answer · answered Jan 06 '16 at 07:07

This is looking for a power of two >= c.

It does this by filling in all the 1's below the top most 1. e.g. 101010 turns into 111111 and then adding 1 at the end to make it 1000000, ie. a power of 2.

It starts by subtracting 1 so that a power of two is left unchanged.

I am not sure why it checks for n >= Integer.MAX_VALUE as an int cannot be > than MAX_VALUE by definition. Perhaps this code was copied from an algo using long n originally.

Note where n > 1 << 30 this will over flow and produce 1 rather than MAX_VALUE.

Why this bit manipulation return this result?

1 Answers1