How to check if a Number is Power of Two in Java? [Bitwise AND Example]

Hello guys, if you are thinking about how to check if a given number is a power of two without using an arithmetic operator like division then you have come to the right place. In Java, you can use bitwise operators like bitwise AND check if a given number if the power of two or if the given number is even or odd. In this Java Programming tutorial, you will learn how to check if the number is the Power of two using a bitwise operator. The main purpose of this program is to teach you how to use bit-wise operators like bitwise AND (&)  in Java. A number is said to be the power of two if all its prime factors are 2, but in the binary world, things work a little differently. 

If you have read the hacker's delight book then you know that there are several techniques to check if a number is the power of two or not, one of them is performing bit-wise AND operation between number and number -1, if the result is zero then the number is the power of two.

Just remember, here we are doing binary subtraction and not decimal one. In bitwise operator, each bit is used in evaluation for example if you use bitwise AND then each bit of both operand will go through AND operation, and the result will contain 1 only if both bits are one otherwise zero. I will explain how exactly this program work, but let's first see the program itself.




Java Program to Check if Number is Power of Two or Not

Here is my solution to this problem. Of course, there are many ways to solve this problem, including by using arithmetic operator as shown in my earlier post, but I have purposefully used bit-wise operator to show how easy and fast is to devise an algorithm using bit-wise operators. This program is a very good example of learning bit-wise operators in Java.

/**
 * Java Program to check if a number is power of two or not.
 *
 * @author Javin
 */
public class PowerOfTwo{

    public static void main(String args[]) {
        System.out.printf("is %d power of Two? %b%n", 2, isPowerofTwo(2));
        System.out.printf("is %d power of Two? %b%n", 4, isPowerofTwo(4));
        System.out.printf("is %d power of Two? %b%n", 5, isPowerofTwo(5));
        System.out.printf("is %d power of Two? %b%n", 1, isPowerofTwo(1));
        System.out.printf("is %d power of Two? %b%n", -1, isPowerofTwo(-1));
    }

    /*
     * @return true, if number is power of two, otherwise false.
     */
    public static boolean isPowerofTwo(int number) {
        return (number & (number - 1)) == 0;
    }

}

Output
is 2 power of Two? true
is 4 power of Two? true
is 5 power of Two? false
is 1 power of Two? true
is -1 power of Two? false





Explanation :

Though this solution is just a beautiful one-liner, it may take some time for you to understand what's happening. To make it simple, let's start with the code itself number & (number - 1)) == 0, So what are we doing here? 

Basically, we are checking if the number & (number - 1) is equal to zero then the number is the power of two. We are doing two operations in this code, the first is binary subtraction and the second is bitwise AND operation.

Let's first see how bitwise AND operator works. As name suggests it performs AND operation on every single bit of both operands, bit-wise, AND will return 0 only if both operands don't have a set bit (1) at the same location. 

In other words, if the first operand has 0 at LSB then the second operand must have 1 or vice-versa, but they must not have 1 at the same position. Now let's come back to binary subtraction,  If you do binary subtraction by hand, you will realize that it at least change your LSB from 0 to 1, and can switch the bit until it encounters a 1 as shown below

 1000
- 0001
-------
  0111
So in order for a number to be a power of two, it must follow a pattern where if number = abcd1000 then n-1 = abcd0111, and abcd must be zero.

How to check if number is power of two in Java

Since any binary number, which is the power of two has exactly one set bit and subtracting one from that will make all lower bits 1, (number & (number-1) will always be zero for a number which is the power of two.

That's all about how to find if a number is the power of two in Java. As I said, there are multiple ways to solve this problem, you can either use arithmetic operator e.g. division or modulo operator or you can simply use bit-wise operator, just like I have used here.  If you are also serious about improving your knowledge of bitwise operators, then you should read hacker's delight, a great book for programmers.

Other Data Structure Problem for Practice 

  • How to check if a given number is prime or not? (solution)
  • How to solve the FizzBuzz problem in Java? (solution)
  • Top 10 Programming problems from Java Interviews? (article)
  • Write code to implement the Quicksort algorithm in Java? (algorithm)
  • 7 Best Courses to learn Data Structure and Algorithms (best courses)
  • 100+ Data Structure and Algorithms Problems (solved)
  • 10 Books to learn Data Structure and Algorithms (books)
  • Write a program to print the highest frequency word from a text file? (solution)
  • How to remove duplicate elements from ArrayList in Java? (solution)
  • How to print the Pyramid pattern in Java? (solution)
  • How do you swap two integers without using a temporary variable? (solution)
  • Write a program to check if a number is the power of two or not? (solution)
  • 10 Free Courses to learn Data Structure and Algorithms (courses)
  • How to find if given String is a palindrome in Java? (solution)
  • How do you reverse word of a sentence in Java? (solution)
  • How to find duplicate characters from String in Java? (solution)
  • How to reverse an int variable in Java? (solution)
  • How to check if a year is a leap year in Java? (answer)
  • How to find a missing number in a sorted array? (solution)
  • How to calculate factorial using recursion and iteration? (solution)
  • Write code to implement the Bubble sort algorithm in Java? (code)
  • How to reverse String in Java without using StringBuffer? (solution)
  • Write a program to code insertion sort algorithm in Java (program)

If you like this coding problem and want to practice more to improve your coding skill, then you can also search for Java programming exercises in this blog.

No comments:

Post a Comment

Feel free to comment, ask questions if you have any doubt.