Q2: How do you check if an integer is a Power of Two in O(1) time?
A positive integer is a power of two if it has exactly one set bit in its binary representation. Evaluating (n > 0) && ((n & (n - 1)) == 0) checks this property in constant time.
Power of Two Check
public class PowerOfTwo {
public static boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}💡 Returns true strictly for positive integers containing a single 1 bit.
Key Takeaways
- Powers of 2 have exactly one bit set to 1 in binary.
(n & (n - 1)) == 0clears that single set bit, resulting in 0.
Knowledge Check
Why is the condition n > 0 mandatory in the expression n > 0 && (n & (n - 1)) == 0?