CODEWITHSUNDEEP
javabitwise-operators
krishna
krishna

Reputation: 65

The code below returns whether the given number is a power of two or not. How does it work?

I can understand that it uses bit-wise AND operator, but how does it work?

public static void main(String[] args) {
  Scanner sc = new Scanner(System.in); 
  long num1=sc.nextLong();
  long count=(num1 & (num1- 1));
  if(count == 0l) {
    System.out.println("power of two");
  }
}

Upvotes: 0

Views: 58

Answers (3)

Aleksandr Erokhin
Aleksandr Erokhin

Reputation: 1982

It is all about the nature of a binary representation of an integer value.

In every positional notation same symbols are used for the different orders of magnitude. In a binary representation symbol 1 is used for magnitudes of 2 depending on its position. This way any integer number could be represented as a sum of powers of 2:

510 = 1012 = 1 * 22 + 0 * 21 + 1 * 20

It is not hard to see that for representing a power of 2 only one symbol of 1 is required at the corresponding position. So the code:

num1 & (num1 - 1)

simply checks that there was only 1 bit set to 1 in a binary representation of the value.

Upvotes: 0

RealSkeptic
RealSkeptic

Reputation: 34628

Powers of two always have just one bit that is "1":

20 = 1 → 0000 0001
21 = 2 → 0000 0010
22 = 4 → 0000 0100
23 = 8 → 0000 1000

... and so on.

Any other number will have at least two "1" bits. For example, the number 6 is 0110, the number 9 is 1001 and so on.

When you subtract one from a number, either you have 1 in the rightmost position:

 00000101
-00000001
 ────────
 00000100

or you'll need to borrow from another 1 to the left.

 00010100
-00000001
 ────────
 00010011

This means that effectively, the first "1" from the right will not be in the result, and all the digits to its right will become "1". All the digits to its left are unchanged.

So if there was only one "1" in the initial number - it was a power of 2 - then we will have 0 where the 1 was. With an &, what you get is:

23 = 8 → 0000 1000
    -1 → 0000 0111
    &8 → 0000 0000

All the bits that were zero in the original 8 will be zero after the &. And we know that subtracting puts zero where the first "1" was. So that too will become zero after the &. Result: the whole number is zero.

But if the number is not a power of 2, it has another "1" bit to the left of the one that gets borrowed by the subtraction. That "1" bit is not going to change:

 24 → 0001 1000
 -1 → 0001 0111
&24 → 0001 0000

The right side, all the way up to the first original "1" are now zero. But as we noticed, the bits to the left of the first "1" are not changed, they were not borrowed. So when you do an & on the bits to the left, you still get "1" in the result.

So the result in such a case will not be zero.

Thus, when you do n & (n-1), if n is not a power of 2, you'll have more than one "1" bit, and the result is non-zero. If it is a power of 2, you'll have just one "1" bit, and the result will be zero.

Upvotes: 1

Eran
Eran

Reputation: 393851

If num is a power of 2, num & (num1 -1) is 0, since num-1 will have 1 bits where num has 0 bits and 0 bit where num has 1 bit.

If num is a power of 2, it has a single 1 bit :

num           00..00100000000..00
num-1         00..00011111111..11
num & (num-1) 00..00000000000..00

If num is not a power of 2, there are at least two 1 bits in num. If you examine the first and last of them, you get :

num           00..001xx..xxx10..0
num-1         00.0001xx..xxx01..1
num & (num-1) 00.0001xx..xxx00..0

So num & (num-1) has at least one 1 bit.

Upvotes: 6

Related Questions