Power Of Two (Exercise Problem)

Create Functional Interface

Let us see an example by creating our own functional interface and doing some checks with the given data.

Problem Statement

Write a program to check if a given number is a power of 2 or not.

Input = 64
 
Output: True

Explanation: We solve by making use of the & operator in computers. There are many ways to solve this, of which two approaches are simple, and one of them is a more complex but better solution.

Assume n is non-negative. Use the & operator to achieve this.

Algorithm

1. Read the input value.
2. Repeatedly divide input with 2.
   • if n is not equal to 1 and if it is odd, we will return false.
   • else true.

Here is what our algorithm will look like:

private static boolean helper(int n) {
  if (n == 0) {
    return false;
  }
  
  while (n != 1) {
    if (n % 2 != 0) {
      return false;
    }
        
    n >>= 1;
  }
    
  return true;
}

Wait! Is this a better approach? an optimized solution? Nope, can we do better?

Yes, we can do better using the Bit Manipulation technique & operator. Let us see the following code which is optimized and takes O(1) time complexity and O(1) space complexity.

Let us try to implement our own functional interface with the problem given using a lambda expression.

If you do not understand the following example, that’s totally normal. We will dive more into lambda expressions in the next lessons.

For now, here are some notes for your understanding.

Optimized Solution: Brian Kernighan’s algorithm

This is considered faster than the previous naive approach.

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:

2⁰, 2¹, 2², 2³, 2⁴, and so on.

Basics Of AND Operator (&)

The Bitwise AND operator is denoted by &. When an AND gate is given with two inputs, the corresponding output will be:

• If two input bits are 1, the output is 1.
• In all other cases its 0, for example
  • 1 & 0 => yields to 0.
  • 0 & 1 => yields to 0.
  • 0 & 0 => yields to 0.

Brian Kernighan’s algorithm 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:

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.

Coding exercise

// DEFINE-YOUR-OWN FUNCTIONAL-INTERFACE
// WRITE-A-METHOD-THAT-RUNS-THE-EXECUTION

Now, try to come up with an approach. This problem is designed for your practice, so try to solve it yourself first. If you get stuck, you can always refer to the solution below. Good luck!

Hint: Read the functional interface declaration and implementations in previous lessons to implement this.

First, look at these code snippets below and think of a solution.

The solution will be explained below.

@FunctionalInterface
public interface PowerOfTwoFI {
    boolean isPowerOfTwo(int number);
}

public class Solution {
  public static void main(String[] args) {
    PowerOfTwoFI helper = n -> n != 0 && (n & (n - 1)) == 0; // lambda expression

    System.out.println(helper.isPowerOfTwo(4));
    System.out.println(helper.isPowerOfTwo(3));
    System.out.println(helper.isPowerOfTwo(10));
    System.out.println(helper.isPowerOfTwo(16));
  }
}

If you are interested to learn more about Bit Manipulation tricks, I have got a course here on this website which is Grokking Bit Manipulation For Coding Interviews.

Bonus

Benefits of learning Bit Manipulation Tricks

1. These bit tricks could help in competitive programming is running algorithms mostly in O(1) time.
2. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies.
3. By the time you’ve completed this course, you will be able to solve problems faster with greater efficiency on platforms like LeetCode, HackerRank, HackerEarth, CodeForces, CodeChef, SPOJ, etc.