Prüfen, ob eine Zahl eine Potenz von 2 ist, mithilfe einer einzelnen Bit-Operation
Angenommen, es wird eine positive ganze Zahl n gegeben, und du sollst ermitteln, ob sie eine Potenz von 2 ist. Dies lässt sich mit einer einzigen Bit-Operation erledigen. Betrachtet man die Bitdarstellung einer Zahl, die eine Potenz von 2 darstellt, so enthält sie in ihrer Darstellung genau eine 1, während alle anderen Bits 0 sind.
Zahl | Binärdarstellung |
|---|---|
8 | 1000 |
32 | 100000 |
128 | 10000000 |
Zufallszahl | Binärdarstellung |
|---|---|
7 | 111 |
67 | 1000011 |
144 | 10010000 |
Das ergibt sich aus der Definition der Binärdarstellung. Jeder Bitplatz, der eine 1 enthält, entspricht der Addition dieser Potenz von 2 (67 = 1 + 2 + 0 + 0 + 0 + 0 + 64, 8 = 0 + 0 + 0 + 8). Wenn eine Zahl in ihrer Binärdarstellung nur eine einzige 1 aufweist, bedeutet das, dass keine weiteren Potenzen von 2 in der Summe vorkommen. Das Problem reduziert sich also darauf zu prüfen, ob genau eine 1 in der Binärdarstellung von n enthalten ist.
Eine leicht zugängliche Methode dafür ist ein bitweises & zwischen n und n-1. Wenn das Ergebnis 0 ist ⇒ handelt es sich um eine Potenz von 2.
Für jede Zahl, die keine Potenz von 2 ist, weicht das Ergebnis von n & (n-1) von 0 ab:
7 & 6 = 111 & 110 = 110 (6)
67 & 66 = 1000011 & 1000010 = 1000010 (66)
144 & 143 = 10010000 & 10001111 = 10000000 (128)
Hingegen gilt für Zahlen, die eine Potenz von 2 sind, immer 0:
8 & 7 = 1000 & 111 = 0
32 & 31 = 100000 & 11111 = 0
128 & 127 = 10000000 & 1111111 = 0
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (2 ≤ n ≤ ).
Ausgabe
Das Programm soll Yes ausgeben, falls n eine Potenz von 2 ist, und No andernfalls.
Beispiele
Input | Output |
|---|---|
8 | Yes |
17 | No |
2048 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB