0

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 は型のビット数です。一定時間回答していただきたいです。

4

2 に答える 2

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];
}
于 2013-04-05T12:46:37.947 に答える