Ich muss etwas Logik schreiben, um eine gerade Zahl zu bestimmen. Die höchste Macht von zwei, die es gleichmäßig teilt. Was ist der Maximalwert von 2 ^ n wo Eingabe% 2 ^ n == 0?
IE:
Eingabe - & gt; Ausgabe
Es sieht so aus, als gäbe es eine bitweise Logik, die funktionieren könnte: Wenn man sich die Eingabe im Binärformat anschaut, erscheint das rechte Bit als Lösung. Wie ermittle ich diesen Wert in C? Gibt es eine andere Lösung, die einfacher sein könnte?
Danke Jonathan
Wenn Sie bereit sind, die Zweierkomplementarithmetik anzunehmen:
x & -x
Wenn Sie so etwas tun (oder auch nur, wenn Sie es interessant finden), finden Sie sich eine Kopie des Buches "Hacker's Delight".
edit: Avakar stellt korrekt fest, dass dies nicht vom Zweierkomplement abhängt, wenn der Typ unsigniert ist. Der relevante Abschnitt der Norm ist § 6.2.5, Absatz 9:
Eine Berechnung mit unsigned Operanden können niemals überlaufen, weil a Ergebnis, das nicht dargestellt werden kann Der resultierende vorzeichenlose Integertyp ist reduziert modulo die Zahl, die eins ist größer als der größte Wert, der kann durch das resultierende dargestellt werden Geben Sie ein.
"Einer, der größer ist als der größte Wert" lässt etwas Spielraum für eine besonders perverse Implementierung (insbesondere eine Implementierung, die beispielsweise keine Binärdatei verwendet), aber das ist ziemlich unwahrscheinlich.
>Ohne Gleitkommaarithmetik zu verwenden:
%Vor%Vereinfachungen und Edge Cases bleiben als Übungen für den Leser übrig.
Wir können (-x) durch (~x + 1) ersetzen:
Low Level Bit Hacks, die du unbedingt kennen musst bietet eine detaillierte Erklärung.
Eine Zahl in der Form 2 ^ n wird binär durch eine 1 geschrieben, gefolgt von einer Folge von 0 oder mehr 0s. Zum Beispiel, 1, 10, 100, 1000, ... usw. sind alle zwei Potenz.
Um die höchste Potenz von 2 zu erhalten, die eine gegebene Zahl teilt, können Sie die folgenden zwei Schritte ausführen:
Schreibe die Zahl in binärer Form. Beispiel: Wenn die Zahl 168 ist, schreiben Sie 10101000.
Streichen Sie alle Bits vor dem ersten Bit von der rechten Seite ab, die 1 enthält. Im Fall von 168 bleibt 1000 (= 8 in Dezimal) übrig, nachdem der erste Teil von 10101000 abgeklopft wurde.
>Was bleibt, ist Ihr Ergebnis - das heißt, die höchste Potenz von 2, die die Zahl teilt.
Programmgesteuert ist x die Eingangsnummer. Dann ist Ihre gewünschte Ausgabe: x - (x ^ (x-1))
Erläuterung:
x ^ (x-1) [bedeutet x XOR x-1] wird die erste 1 von der LSB (least significant bit) -Seite los.
x - (x ^ (x-1)) entfernt den verbleibenden Teil und behält nur die erste 1 von der LSB-Seite bei.
Tags und Links c bit-manipulation