Power of Two

To determine if an integer n is a power of two, you can use bitwise operations. A number that is a power of two has exactly one ‘1’ bit in its binary representation. When you subtract 1 from such a number, all the bits to the right of that ‘1’ bit will be flipped. By using the bitwise AND operation between n and n-1, you will get 0 if n is a power of two.

Here’s a code example:

1
2
3
4
5
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        return (n & (n - 1)) == 0

The condition n <= 0 handles the constraint that n must be positive to be a power of two. If n is positive and a power of two, (n & (n - 1)) will be 0, so the function returns True. Otherwise, it returns False.

This code runs in O(1) time complexity.

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

x = 8

0000 1000 (x=8) 1111 0111 (compliment of 8) 1111 1000

0000 1000

0000 0100 1111 1011 1111 1100

0000 0100

0000 0100 1111 1011

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# @param {Integer} n
# @return {Boolean}
def is_power_of_two(n)
   if n == 0
       return false
   end
   n & (~n+1) == n
end

def is_power_of_two(n)
   if n == 0
       return false
   end
   n & (-n) == n
end

Problem Classification

Mathematical problem: The nature of the problem is mathematical as it involves understanding the properties of numbers and the binary numeral system.
Bit manipulation problem: The core of the problem involves using bitwise operators to manipulate the bits of a number. Specifically, it uses a property of numbers that are powers of two when represented in binary format.
Boolean Logic problem: The solution relies on understanding and correctly applying logical operations, specifically the AND operation.

The classification revolves around mathematical properties and operations, binary representations of numbers, and logical operators.

Language Agnostic Coding Drills

Understanding the problem: Recognize the problem as a mathematical property check problem where you need to check if a given number is a power of two.
Bitwise operations: Understand the concept of bitwise operations. This problem requires the knowledge of bitwise AND operation.
Representation of numbers in binary: Understand how numbers are represented in binary. A power of two in binary format always has one bit set to 1 and the rest of the bits set to 0.
Property of (n-1): Know that for a number which is a power of two, subtracting 1 from it will flip the bits after the bit which is set to 1.
Combining the concepts: Know how to combine these concepts and come up with the condition that a number is a power of two if and only if n>0 and n&(n-1) equals 0.
Boolean operations: Understand that the ‘and’ operation in the condition is a logical ‘and’, which returns True only if both conditions are met.

The sequence of drills:

Drill 1: Understand the problem
Drill 2: Learn about bitwise operations
Drill 3: Learn about binary representation of numbers
Drill 4: Understand the property of (n-1) for power of two
Drill 5: Understand how to combine these concepts
Drill 6: Learn about logical operations

Once these concepts are learned and understood, they can be combined to create the final solution.

Targeted Drills in Python

Drill 1: Understand the problem This is a theoretical step. No code is required.

Drill 2: Learn about bitwise operations For this drill, we’ll focus on bitwise AND operation. The bitwise AND operation takes two numbers as operands and does AND on every bit of the two numbers. The result of AND is 1 only if both bits are 1.

1
2
3
4
def bitwise_and(x, y):
    return x & y

print(bitwise_and(10, 12))  # Output: 8

Drill 3: Learn about binary representation of numbers Python provides built-in functions to convert an integer to a binary string and vice versa.

1
2
3
4
def binary_representation(n):
    return bin(n)

print(binary_representation(10))  # Output: '0b1010'

Drill 4: Understand the property of (n-1) for power of two In binary, (n-1) would have all the bits same as n, except for the rightmost 1 in n and all the bits to the right of the rightmost 1.

1
2
3
4
def subtract_one(n):
    return bin(n - 1)

print(subtract_one(8))  # Output: '0b111'

Drill 5: Understand how to combine these concepts Combining these concepts, we can see that for a number which is a power of two, subtracting 1 from it will flip all the bits after the bit which is set to 1. Hence the bitwise AND operation of n and (n-1) would be 0.

1
2
3
4
def bitwise_and_after_subtracting_one(n):
    return n & (n - 1)

print(bitwise_and_after_subtracting_one(8))  # Output: 0

Drill 6: Learn about logical operations Python supports all the standard logical operations from mathematics.

1
2
3
4
def logical_and(x, y):
    return x and y

print(logical_and(True, False))  # Output: False

Final Solution Integrate all the drills to write the final solution. This is a combination of Drill 5 and Drill 6:

1
2
3
4
5
6
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0

solution = Solution()
print(solution.isPowerOfTwo(8))  # Output: True