Java: Offset of highest 1 bit in an integer

Question

Let's not consider 0 or negative values for the sake of simplicity.

Known solution #1

return (int)(Math.log(x)/Math.log(2)); // pseudo code

Problem: Numerically unstable. For x=4 input it may answer 2 or 1.

Known solution #2

for(int i=0; ;++i)
{
    x = x >> 1;
    if(x==0)
        return i;
}

Problem: Average complexity is O(n) where n is the number of bits in type. I would like to have constant time answer.

score 3 · Accepted Answer · answered Apr 05 '13 at 12:44

3

There are a number of solutions that are O(log n) (or better!) available at http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

answered Apr 05 '13 at 12:44

Alnitak

334,560
70
407
495

Seeing `O(log n)` alone gave me ideas! :-) – Notinlist Apr 05 '13 at 12:45

score 2 · Answer 2 · answered Apr 05 '13 at 12:46

Here is a constant-time Java solution based on this:

private static final int MultiplyDeBruijnBitPosition[] = new int[] { 0, 9,
        1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28,
        15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 };

public static int top1(int v) {
    v |= v >>> 1;
    v |= v >>> 2;
    v |= v >>> 4;
    v |= v >>> 8;
    v |= v >>> 16;
    return MultiplyDeBruijnBitPosition[(int)((v * 0x07C4ACDDL) >> 27) & 31];
}

Java: Offset of highest 1 bit in an integer

2 Answers2