java - Java：整数中最高 1 位的偏移量

Question

为了简单起见，我们不考虑0负值。

已知解决方案#1

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

问题：数值不稳定。对于x=4输入，它可能会回答 2 或 1。

已知解决方案#2

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

问题：平均复杂度为 O(n)，其中 n 是类型的位数。我想有恒定的时间答案。

Answer 1

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious提供了许多O(log n)（或更好的！）解决方案

Answer 2

这是一个基于此的恒定时间 Java 解决方案：

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];
}