Solution Review: Power of 2
Let's solve this using brain kernighan's algorithm. This is optimized to O(1) time and space.
Table of Contents
Let's see how we use Brain Kernighan's algorithm to achieve this.
Solution review: Brian Kernighan’s algorithm
We saw an algorithm to solve this problem in the previous lesson. Let’s see how to solve this more efficiently using Briann’s Algorithm.
In this approach, we count the set bits. If a number is the power of 2, we know that only one set bit is present in its Binary representation.
In binary, we go from right to left with powers of 2.
For example:
20, 21, 22, 23, 24, and so on...
Algorithm
Before we talk about algorithmic steps, you should review the table data and slider shown below the table.
- if
(n & (n - 1) == 0)
, returntrue
- else,
false
Let’s visualize the values in the table below:
n | n (in binary) | (n - 1) | (n - 1) in binary | n & (n - 1) | (n & (n - 1) == 0) |
---|---|---|---|---|---|
2 | 0010 | (2 - 1) = 1 | 0001 | (2 & 1) = 0 | true |
6 | 0110 | (6 - 1) = 5 | 0101 | (6 & 5) = 4 | false |
8 | 1000 | (8 - 1) = 7 | 0111 | (8 & 7) = 0 | true |
10 | 1010 | (10 - 1) = 9 | 1001 | (10 & 9) = 8 | false |
Let’s see a couple of examples:
n = 4 => 00000000 00000000 00000000 00000100
n - 1 = 3 => 00000000 00000000 00000000 00000011
-----------------------------------------------------------
(n & (n - 1)) = 0 => 00000000 00000000 00000000 00000000
-----------------------------------------------------------
( n & (n - 1))
, here this becomes 0
, which is true. Hence, the number 4
is a power of 2.
n = 6 => 00000000 00000000 00000000 00000110
n - 1 = 5 => 00000000 00000000 00000000 00000101
-----------------------------------------------------------
(n & (n - 1)) = 4 => 00000000 00000000 00000000 00000100
-----------------------------------------------------------
( n & (n - 1))
is 4
, which is not equal to 0
. Hence, the number 6
is not a power of 2.
Solution
Here is the reasoning behind this solution.
Java
class IsPowerOf2 {
public static void main(String[] args) {
System.out.println(helper(6));
System.out.println(helper(8));
}
/**
* Return boolean(even/odd) for the given number.
*
* @param n
* @return
*/
private static boolean helper(int n) {
if (n == 0) {
return false;
}
return (n & (n - 1)) == 0;
}
}
We can further simplify this code into a single line shown below.
class IsPowerOf2 {
public static void main(String[] args) {
System.out.println(helper(6));
System.out.println(helper(8));
}
/**
* Return boolean(even/odd) for the given number.
*
* @param n
* @return
*/
private static boolean helper(int n) {
return n != 0 && (n & (n - 1)) == 0;
}
}
Python
def helper(n):
if n == 0:
return False
return (n & (n - 1) == 0)
print(helper(6))
print(helper(8))
We can further simplify this code into a single line shown below.
def IsPowerOf2(n):
return n != 0 and (n & (n - 1)==0)
print(IsPowerOf2(6))
print(IsPowerOf2(8))
JavaScript
/**
* Return boolean(even/odd) for the given number.
*
* @param {number} number
* @return {boolean}
*/
const IsPowerOf2 = number => {
function helper (n) {
if(n === 0) {
return false;
}
return (n & (n - 1)) === 0;
}
return helper (number);
}
console.log (IsPowerOf2 (6));
console.log (IsPowerOf2 (8));
We can further simplify this code into a single line shown below.
/**
* Return boolean(even/odd) for the given number.
*
* @param {number} number
* @return {boolean}
*/
const IsPowerOf2 = n => {
return n !== 0 && (n & (n - 1)) === 0;
}
console.log (IsPowerOf2 (6));
console.log (IsPowerOf2 (8));
C++
#include <iostream>
using namespace std;
bool helper(int n) {
if (n == 0) {
return false;//0 represents as false and 1 represents as true.
}
return (n & (n - 1)) == 0;
}
int main() {
cout << helper(6) << endl;
cout << helper(8) << endl;
return 0;
}
We can further simplify this code into a single line shown below.
#include <iostream>
using namespace std;
bool helper(int n) {
return n != 0 && (n & (n - 1)) == 0;
}
int main() {
cout << helper(6) << endl;
cout << helper(8) << endl;
return 0;
}
TypeScript
export const IsPowerOf2 = (n: number): boolean => {
function helper(value: number): boolean {
if (value === 0) {
return false;
}
return (value & (value - 1)) === 0;
}
return helper(n);
}
console.log(IsPowerOf2(6));
console.log(IsPowerOf2(8));
We can further simplify this code into a single line shown below.
const IsPowerOf2 = (n: number): boolean => {
return n !== 0 && (n & (n - 1)) === 0;
}
console.log (IsPowerOf2 (6));
console.log (IsPowerOf2 (8));
Complexity analysis
Time complexity: O(1)
The run time depends on the number of 1-bits in n. In the worst case, all bits in n are 1-bits. In the case of a 32-bit integer, the run time is O(1)
.
Space complexity: O(1)
The space complexity is O(1)
. No additional space is allocated.
👨🏻💻 Gopi Gorantala Newsletter
Join the newsletter to receive the latest updates in your inbox.