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 n1
, you will get 0 if n
is a power of two.
Here’s a code example:


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.


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


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 (n1): 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&(n1) 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 (n1) 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.


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


Drill 4: Understand the property of (n1) for power of two In binary, (n1) 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.


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 (n1) would be 0.


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


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

