Power of Two: n and n-1 Pattern

Learning Outcome

After this lesson, you should be able to recognize the one-set-bit property of powers of two.

Problem Statement

Given an integer n, return true if it is a power of two.

Brute Force Approach

Repeatedly divide by 2 until the number becomes odd. This works but is longer and easy to mishandle for zero or negative values.

Optimized Approach

A positive power of two has one set bit. n & (n

• 1. clears the lowest set bit, so the result is zero only when there was one set bit.

Exact Pseudocode

if n <= 0:
  return false
return (n & (n - 1)) == 0
  

Reference Code

class Solution:
    def isPowerOfTwo(self, n):
        return n > 0 and (n & (n - 1)) == 0
  

Sample Dry Run

Complexity

Edge Cases

• Zero is not a power of two.
• Negative numbers are not powers of two.
• Do the n > 0 check before trusting the bit expression.

Interview Checklist

• Remember the one-set-bit property.

• Use n & (n

  • 1. to remove the lowest set bit.
• Guard against n <= 0.

FAQs

0 & -1 is 0, so without n > 0, zero would incorrectly pass.

What does n & (n

• 1. do?

It clears the lowest set bit of n.

Single-set-bit check.