Wie klar das höchstwertige bit?

Edit: Vereinfachte (und erklärt) Antwort

Die Antwort, die ich gab unten übertrieben ist, wenn Ihr nur Ziel ist es, das höchstwertige bit auf null.

Das Letzte bit code erstellt eine bit-Maske, die alle bits der Zahl.

mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;

Hier ist die Reihe von Berechnungen führt es auf eine bestimmte 32-bit unsigned integer:

mask = originalValue
mask:               01000000000000000000000000000000
mask |= mask >> 1:  01100000000000000000000000000000
mask |= mask >> 2:  01111000000000000000000000000000
mask |= mask >> 4:  01111111100000000000000000000000
mask |= mask >> 8:  01111111111111111000000000000000
mask |= mask >> 16: 01111111111111111111111111111111

Da spielt es eine bit-Verschiebung nach rechts, die keinen wrap-around, es wird nie bits, die höher als die am meisten signifikante bit wird auf eins gesetzt. Da ist es mit einem logischen or Sie wird nie explizit gesetzt, werden alle Werte auf null, die nicht bereits null.

Logisch, das wird immer erstellen Sie eine bit-Maske, die füllt die ganze uint, bis zu und einschließlich der meisten signifikante bit, die ursprünglich festgelegt wurde, aber nicht höher.

Aus, dass Maske es ist ziemlich einfach, es zu verkleinern, um alle aber das höchstwertige bit, die ursprünglich festgelegt wurde:

mask = mask >> 1: 00111111111111111111111111111111

Dann nur eine logische and gegen den ursprünglichen Wert, und das wird alle die meisten signifikanten bits in die Anzahl auf null, bis zu und einschließlich des höchstwertigen bit vom ursprünglichen Wert:

originalValue &= mask: 00000000000000000000000000000000

Die ursprüngliche Zahl, die ich hier verwendet zeigt die Maske-building-Prozess gut, aber es nicht zeigen, dass die Letzte Berechnung sehr gut. Können führen Sie durch die Berechnungen mit mehr interessante Beispiel-Werte (in der Frage):

originalValue: 1101
mask = originalValue
mask:               00000000000000000000000000001101
mask |= mask >> 1:  00000000000000000000000000001111
mask |= mask >> 2:  00000000000000000000000000001111
mask |= mask >> 4:  00000000000000000000000000001111
mask |= mask >> 8:  00000000000000000000000000001111
mask |= mask >> 16: 00000000000000000000000000001111
mask = mask >> 1:   00000000000000000000000000000111

Und hier ist der Wert, den Sie suchen:

originalValue &= mask: 00000000000000000000000000000101

Da können wir sehen, das funktioniert, jetzt kommt der endgültige code zusammen:

uint SetHighestBitToZero(uint originalValue)
{
    uint mask = originalValue;

    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;

    mask = mask >> 1;

    return originalValue & mask;
}

//...
Console.WriteLine(SetHighestBitToZero(13)); //1101

5

(was 0101)

Ursprünglichen Antwort, die ich gab

Für diese Art von Fragen, die ich oft mit einem Verweis auf diesen Artikel:

"Bit Twiddling Hacks"

Den besonderen Abschnitt, den Sie wollen, wird als "Suche nach ganzzahligen Logarithmus zur Basis 2 einer Zahl (aka die position des höchsten bit gesetzt)".

Hier ist die erste einer Reihe von Lösungen (jeweils mehr optimal als die Vorherige):

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

Die endgültige Lösung in dem Artikel ist (konvertiert C#):

uint originalValue = 13;
uint v = originalValue; //find the log base 2 of 32-bit v
int r;  //result goes here

uint[] MultiplyDeBruijnBitPosition = 
{
  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
};

v |= v >> 1; //first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = (int)MultiplyDeBruijnBitPosition[(uint)(v * 0x07C4ACDDU) >> 27];

Sobald Sie gefunden haben, das höchste gesetzte bit, einfach die Maske aus:

originalValue &= ~(uint)(1 << r); //Force bit "r" to be zero

int x = 0xD; //01101
int wk = x;
int mask = 1;
while(0!=(wk >>= 1)) mask <<= 1;
x ^= mask; //00101

Wenn Sie als integet dann den code, ist das Ergebnis immer angezeigt werden, ohne die null.kann string-manipulation heraus, was Sie wollen, aber nicht wissen wie, die gehen, um Ihnen zu helfen. Mit string, wird so etwas wie unten:

  string y = "01101";
  int pos = y.IndexOf("1");
  y = y.Insert(pos, "0");
  y = y.Remove(pos + 1, 1);