最大2乗の2進演算に丸めます

Question

与えられた数x xの次の2のべき乗に丸めます。 私は単純な解決策を見つけましたが、 " - "操作なしでそれを解決することが可能かどうか、 >>、>>>、< <および|オペレーション。ここ は私のコードです：それはバージョン1に非常に近いですが

バージョン1

public static int maxPowerOf2(int x) 
    { 
    x |= x >> 1; 
    x |= x >> 2; 
    x |= x >> 4; 
    x |= x >> 8; 
    x |= x >> 16; 
    return x - (x >> 1); 
    } 

バージョン2

public static int maxPowerOf2(int x) 
{ 
    int v=x; 
    v |= v >> 1; 
    v |= v >> 2; 
    v |= v >> 4; 
    v |= v >> 8; 
    v |= v >> 16; 
    v= v>>1; 

    int m16=~v; 
    v=v<<1; 
    v=v&m16; 

    return v; 
} 

Answer 1

はここ..だけの二項演算を使用してソリューションです：

public static int maxPowerOf2(int x) { 
    x |= x >> 1; 
    x |= x >> 2; 
    x |= x >> 4; 
    x |= x >> 8; 
    x |= x >> 16; 
    return x^(x >> 1); 
} 

この文脈では、^はariと同じことを達成しますthmetic subtraction

Answer 2

あなたが探しているのは、xに設定されている最上位ビットを特定することです。
コードは32ビット値でこれを行うための変形です。

最速の解決策は、ルックアップテーブルを使用することです。ほとんどの場合、バイナリ検索ツリーを使用しています。別名：

int v = x: 
int r = 0; 
int shift = 0; 
r =  (v > 0xFFFF) ? 1 << 4 : 0; v >>= r; 
shift = (v > 0xFF ) ? 1 << 3 : 0; v >>= shift; r |= shift; 
shift = (v > 0xF ) ? 1 << 2 : 0; v >>= shift; r |= shift; 
shift = (v > 0x3 ) ? 1 << 1 : 0; v >>= shift; r |= shift; 
r |= (v >> 1); 

あなたの結果を保持します。あなたの代わりに-のそして、あなたは^（XOR）を使用することができませんしてください0xFFFFFFFF

を使用してレベルを追加する必要がありますlong型で

。あなたのケースで減算を避けるために。