Is a power of two
Algorithm · Starter
Step through it: Bit Manipulation pattern
Step 1 of 5
Goal: every number appears twice except one. Find the odd one out without extra memory. Trick: the XOR operation (^) turns two equal numbers into 0, and anything XOR 0 stays itself. So XOR everything together and the pairs vanish.
Step 2 of 5
Start with 0. Then 0 ^ 4 = 4.
Step 3 of 5
4 ^ 1 = 5, then 5 ^ 2 = 7.
Step 4 of 5
7 ^ 1 = 6, then 6 ^ 2 = 4. The 1s and 2s cancelled each other out. The answer is 4, in one pass with no extra memory. Working directly on the bits of numbers is bit manipulation.
Step 5 of 5
Your turn.
Given a positive integer, write a function to find if it is a power of two or not.
Naive solution
In naive solution we just keep dividing the number by two
unless the number becomes 1 and every time we do so, we
check that remainder after division is always 0. Otherwise, the number can't be a power of two.
Bitwise solution
Powers of two in binary form always have just one bit set.
The only exception is with a signed integer (e.g. an 8-bit
signed integer with a value of -128 looks like: 10000000)
1: 0001
2: 0010
4: 0100
8: 1000So after checking that the number is greater than zero, we can use a bitwise hack to test that one and only one bit is set.
number & (number - 1)For example for number 8 that operations will look like:
1000
- 0001
----
0111
1000
& 0111
----
0000Code
/**
* @param {number} number
* @return {boolean}
*/
export default function isPowerOfTwo(number) {
// 1 (2^0) is the smallest power of two.
if (number < 1) {
return false;
}
// Let's find out if we can divide the number by two
// many times without remainder.
let dividedNumber = number;
while (dividedNumber !== 1) {
if (dividedNumber % 2 !== 0) {
// For every case when remainder isn't zero we can say that this number
// couldn't be a result of power of two.
return false;
}
dividedNumber /= 2;
}
return true;
}/**
* @param {number} number
* @return {boolean}
*/
export default function isPowerOfTwoBitwise(number) {
// 1 (2^0) is the smallest power of two.
if (number < 1) {
return false;
}
/*
* Powers of two in binary look like this:
* 1: 0001
* 2: 0010
* 4: 0100
* 8: 1000
*
* Note that there is always exactly 1 bit set. The only exception is with a signed integer.
* e.g. An 8-bit signed integer with a value of -128 looks like:
* 10000000
*
* So after checking that the number is greater than zero, we can use a clever little bit
* hack to test that one and only one bit is set.
*/
return (number & (number - 1)) === 0;
}References
Practice
Bit Manipulation
- Single NumberEasy
- Number of 1 BitsEasy
- Power of TwoEasy
- Counting BitsEasy
- Reverse BitsEasy
- Missing NumberEasy
- Hamming DistanceEasy
- Single Number IIMedium
- Single Number IIIMedium
- Sum of Two IntegersMedium
- Bitwise AND of Numbers RangeMedium
- SubsetsMedium
- Maximum Product of Word LengthsMedium
- Maximum XOR of Two Numbers in an ArrayHard
Spotted a mistake or something unclear? Report it on GitHub.