The problem
Decide whether n is a power of two.
Input: 16 Output: true
Picture it
Picture a switch panel: a power of two has exactly one switch on. n & (n − 1) turns off the lowest switch; if nothing is left, there was only one.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
n > 0 and n & (n − 1) == 0. O(1).
Python solution
def is_power_of_two(n):
return n > 0 and n & (n - 1) == 0In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.