Runde auf die höchste Potenz von 2 nur binäre Operationen

Question

Gegeben eine Zahl x Runde auf die höchste Potenz von 2, die nicht höher als x ist. Ich fand eine einfache Lösung, aber ich frage mich, ob es möglich ist, es ohne "-" Operation zu lösen, nur mit >>, >>>, < < und | Operationen. Hier ist mein Code:

Version 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); 
    } 

Version 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

Hier eine Lösung ist nur binäre Operationen mit .. obwohl es auf Version sehr nahe 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); 
} 

In diesem Zusammenhang erreicht ^ das gleiche wie ari Thmetic Subtraktion

Answer 2

Was Sie suchen, ist die höchste Bit-Set in Ihrem x identifiziert.
Ihr Code ist eine Variante, um dies für 32-Bit-Werte zu tun.

Die schnellste Lösung wäre die Verwendung einer Nachschlagetabelle. Am praktischsten ist die Verwendung eines binären Suchbaums. aka:

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); 

r wird Ihr Ergebnis halten.

Mit sehnt man braucht eine Ebene hinzufügen 0xFFFFFFFF mit

Und bitte nicht können Sie ^ (XOR) statt - verwenden. um Subtraktion in Ihrem Fall zu vermeiden. (Dies würde jedoch nicht wirklich Kosten verursachen)