Skip to interview prep
Apexed

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.

How do you test whether an integer is a power of two in O(1) — Data structures & algorithms interview question — Apexed