Beginner LevelData Structures & Algorithms
How do you check if a number is a Power of Two using bit manipulation?
ā Interview Prompt: Implement efficient power-of-two check using bitwise AND trick and explain why it works.
Key Insight: A power of two in binary has exactly one set bit.
ā¢
$1 = 0001$, $2 = 0010$, $4 = 0100$, $8 = 1000$.
Trick: $N$ & $(N - 1)$ clears the lowest set bit of $N$.
ā¢
For a power of two, this equals $0$ (only one bit ā cleared completely).
ā¢
For non-powers (e.g., $6 = 0110$): $6$ & $5 = 0110$ & $0101 = 0100 \neq 0$.
isPowerOfTwo(N) = N > 0 && (N & (N-1)) === 0
Code Implementation Example
typescript
function isPowerOfTwo(n: number): boolean {
return n > 0 && (n & (n - 1)) === 0;
}
// Explanation:
// n=8: 1000 & 0111 = 0000 ā true
// n=6: 0110 & 0101 = 0100 ā false
// n=1: 0001 & 0000 = 0000 ā true (2^0 = 1)
console.log(isPowerOfTwo(16)); // true
console.log(isPowerOfTwo(18)); // false
// Count set bits (Hamming Weight) with same trick
function countBits(n: number): number {
let count = 0;
while (n > 0) { n &= n - 1; count++; }
return count;
}š”Bit manipulation O(1) power-of-two check and bit count.
šÆ Interview Key Takeaway
n & (n-1) is a fundamental bit trick that clears the lowest set bit. Powers of two have exactly one set bit, making the result 0.
#DSA#Bit Manipulation#Powers of Two#Bitwise#Beginner
Back to all Data Structures & Algorithms Questionsā