In this Java Programming tutorial you will learn how to check if number is Power of two using bitwise operator. Main purpose or this program is to teach you how to use bit-wise operators like bitwise AND (&) in Java. A number is said to be power of two if all its prime factors are 2, but in binary world things works little differently. If you have read hacker's delight book then you know that there are several technique to check if a number is power of two or not, one of them is performing bit-wise AND operation between number and number -1, if result is zero then number is 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 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.

##

Here is my solution of 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 operator in Java.

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 wee are checking if number & (number - 1) is equal to zero then number is power of two. We are doing two operation in this code, first is binary subtraction and second is bitwise AND operation. Let's first see how bitwise AND operator works. As name suggest it performs AND operation on every single bit of both operand, bit-wise AND will return 0 only if both operand don't have a set bit (1) at same location. In other words, if first operand has 0 at LSB then second operand must have 1 or vice-versa, but they must not have 1 at 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 encounter 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.

Since any binary number, which is 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 number which is power of two.

That's all about

The Coding Interview Bootcamp: Algorithms + Data Structures

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

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.

##
__Java Program to Check if Number is Power of Two__

Here is my solution of 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 operator 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 wee are checking if number & (number - 1) is equal to zero then number is power of two. We are doing two operation in this code, first is binary subtraction and second is bitwise AND operation. Let's first see how bitwise AND operator works. As name suggest it performs AND operation on every single bit of both operand, bit-wise AND will return 0 only if both operand don't have a set bit (1) at same location. In other words, if first operand has 0 at LSB then second operand must have 1 or vice-versa, but they must not have 1 at 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 encounter 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.

Since any binary number, which is 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 number which is power of two.

That's all about

**how to find if a number is 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 on bitwise operator, then you should read hacker's delight, a great book for programmers.**Further Learning**The Coding Interview Bootcamp: Algorithms + Data Structures

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

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.