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
💡
Intuition
Betrachtet man die Zahlen
n und n-1, so bleibt das höchstwertige Bit nur dann erhalten, wenn die Binärdarstellung von n weitere 1en neben dem höchstwertigen Bit aufweist. Ist n eine Potenz von 2 ⇒ dann enthält die Binärdarstellung genau eine einzige 1, und beim Subtrahieren von 1 geht dieses höchstwertige Bit verloren (es wird zu 0 und alle anderen Bits werden zu 1).
Handelt es sich um andere Zahlen (6, 67, 144 usw.), so haben ihre Binärdarstellungen mehrere 1en. Entsprechend wird beim Subtrahieren von 1 nicht das höchstwertige Bit entfernt.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