410. How do you test whether an integer is a power of two in O(1)?
EasyAlgorithm analysis
Technical
Show model answer
A power of two has exactly one set bit, and subtracting 1 turns that bit off and sets all bits below it, so `n > 0 && (n & (n - 1)) === 0` is true exactly for powers of two. The `n > 0` check rules out zero (and negative numbers in two's complement). It is O(1) time and space.
Related tricks: `n & -n` isolates the lowest set bit; a power of four is a power of two whose bit sits at an even position (`(n & 0x55555555) !== 0` for 32-bit values); and rounding up to the next power of two can be done by smearing bits right with shifts and ORs and then adding 1.