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.

Java67

Pages

Saturday, August 20, 2022

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

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

Explanation :

Other Data Structure Problem for Practice

No comments:

Post a Comment

Get new posts by email: