Skip to main content

AND Operator

Solution Review: Power of 2

3 min read

Let's solve this using brain kernighan's algorithm. This is optimized to O(1) time and space.

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), return true
  • else, false

Let’s visualize the values in the table below:

nn (in binary)(n - 1)(n - 1) in binaryn & (n - 1)(n & (n - 1) == 0)
20010(2 - 1) = 10001(2 & 1) = 0true
60110(6 - 1) = 50101(6 & 5) = 4false
81000(8 - 1) = 70111(8 & 7) = 0true
101010(10 - 1) = 91001(10 & 9) = 8false

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.

Reading Progress