Studie die folgenden zwei Funktionen:
bool GetBit(int value, int bit_position)
{
return value & (1 << bit_position);
}
void SetBit(int& value, int bit_position, bool new_bit_value)
{
if (new_bit_value)
value |= (1 << bit_position);
else
value &= ~(1 << bit_position);
}
So, jetzt können wir beliebige Bits lesen und schreiben wie ein Array.
1 << N
gibt Ihnen:
000...0001000...000
Wo die 1 in der N-ten Position befindet.
So
1 << 0 == 0000...0000001
1 << 1 == 0000...0000010
1 << 2 == 0000...0000100
1 << 3 == 0000...0001000
...
und so weiter.
Nun, was passiert, wenn ich BINARY UND eine der oben genannten Nummern mit einer anderen Nummer Y?
X = 1 << N
Z = X & Y
Wie wird Z aussehen? Nun, jedes bisschen abgesehen von der Nth wird definitiv 0 sein, nicht wahr? weil diese Bits in X 0 sind.
Was wird das N-te Bit von Z sein? Es hängt vom Wert des N-ten Bits von Y ab, nicht wahr? Also unter welchen Umständen ist Z Null? Genau, wenn das N-te Bit von Y 0 ist. Indem wir also Z in ein bool umwandeln, können wir den Wert des N-ten Bits von Y trennen. Sehen Sie sich die obige GetBit-Funktion genauer an, das ist genau das, was sie tut.
Jetzt lesen Bits, wie setzen wir ein bisschen? Nun, wenn wir wollen, ein Bit, auf uns Binär- oder mit einem der (1 < < N) Zahlen von oben verwenden:
X = 1 << N
Z = Y | X
Was ist Z hier zu sein? Nun, jedes Bit wird das gleiche wie Y außer der N-ten oder? Und das N-te Bit wird immer 1 sein. Also haben wir das N-te Bit eingeschaltet.
Wie wäre es, ein Bit auf Null zu setzen? Was wir tun wollen, ist eine Nummer wie 11111011111, wo nur das N-te Bit aus ist und dann BINARY AND. Um eine solche Zahl, die wir nicht nur BINARY verwenden:
X = 1 << N // 000010000
W = ~X // 111101111
Z = W & Y
So werden alle Bits in Z abgesehen von der N-ten werden Kopien von Y. sein Die Nth wird immer ausgeschaltet sein. Also haben wir effektiv das N-te Bit auf 0 gesetzt.
Mit den obigen zwei Techniken haben wir SetBit implementiert.
So jetzt können wir beliebige Bits lesen und schreiben. Jetzt können wir die Bits der Zahl genau wie ein Array umkehren:
int ReverseBits(int input)
{
int output = 0;
for (int i = 0; i < N; i++)
{
bool bit = GetBit(input, i); // read ith bit
SetBit(output, N-i-1, bit); // write (N-i-1)th bit
}
return output;
}
Bitte stellen Sie sicher, dass Sie alles verstehen. Sobald Sie alles verstanden haben, schließen Sie bitte die Seite und implementieren und testen Sie sie, ohne sie anzusehen.
Wenn Sie genossen dies als einige von ihnen versuchen:
http://graphics.stanford.edu/~seander/bithacks.html
und/oder dieses Buch:
http://www.amazon.com/exec/obidos/ASIN/0201914654/qid%3D1033395248/sr%3D11-1/ref%3Dsr_11_1/104-7035682-9311161
Was war der Code, den Sie verwendet, und was ist ein Beispiel für eine Eingabe, für die es nicht funktioniert hat? –
Sie denken über dieses Problem alles falsch. Denken Sie nicht an 16 Hex-Zahlen - was bedeutet das überhaupt? Stellen Sie sich das als Umkehrung von Bits in einer 8-Bit-Ganzzahl vor. Ich habe dir in der Antwort unten viele Treffer gegeben. –
Wenn es hilft, hat der & Operator eine ziemlich nette Verwendung, die Sie auf eine Art zur Lösung dieses Problems bringen konnte. – chris