50

Possible Duplicates:
Query about working out whether number is a power of 2
What does this function do?

n & (n-1) - where can this expression be used ?

Community
  • 1
  • 1
Vishwanath Dalvi
  • 35,388
  • 41
  • 123
  • 155
  • Check this question: http://stackoverflow.com/questions/3265942/what-does-this-function-do/3265978 – Vladimir Jan 13 '11 at 09:12
  • 2
    @Paul R, to me it is not a duplicate (albeit related) - this one comes from the other way around, one might say. – Péter Török Jan 13 '11 at 09:25
  • 1
    It turns the rightest 1 into 0 of n's binary mode. If the result equals 0, which means there is only one 1 in n's binary mode, which means n is power of 2. – shellbye Nov 12 '19 at 12:34

4 Answers4

80

It's figuring out if n is either 0 or an exact power of two.

It works because a binary power of two is of the form 1000...000 and subtracting one will give you 111...111. Then, when you AND those together, you get zero, such as with:

  1000 0000 0000 0000
&  111 1111 1111 1111
  ==== ==== ==== ====
= 0000 0000 0000 0000

Any non-power-of-two input value (other than zero) will not give you zero when you perform that operation.

For example, let's try all the 4-bit combinations:

     <----- binary ---->
 n      n    n-1   n&(n-1)
--   ----   ----   -------
 0   0000   0111    0000 *
 1   0001   0000    0000 *
 2   0010   0001    0000 *
 3   0011   0010    0010
 4   0100   0011    0000 *
 5   0101   0100    0100
 6   0110   0101    0100
 7   0111   0110    0110
 8   1000   0111    0000 *
 9   1001   1000    1000
10   1010   1001    1000
11   1011   1010    1010
12   1100   1011    1000
13   1101   1100    1100
14   1110   1101    1100
15   1111   1110    1110

You can see that only 0 and the powers of two (1, 2, 4 and 8) result in a 0000/false bit pattern, all others are non-zero or true.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • 1
    How come 7 and -1 both have 0111? – sofs1 Oct 16 '18 at 03:59
  • 1
    `n & (n-1)` helps in identifying the value of the last bit. Since the least significant bit for n and n-1 are either (0 and 1) or (1 and 0) . Refer above table. `(n & (n-1)) == 0` only checks if n is a power of 2 or 0. – sofs1 Oct 16 '18 at 07:57
  • It's a problem from [leetcode](https://leetcode.com/problems/power-of-two/) – Jerry An Feb 09 '21 at 09:06
9

It returns 0 if n is a power of 2 (NB: only works for n > 0). So you can test for a power of 2 like this:

bool isPowerOfTwo(int n)
{
    return (n > 0) && ((n & (n - 1)) == 0);
}
Paul R
  • 208,748
  • 37
  • 389
  • 560
4

It checks if n is a power of 2: What does the bitwise code "$n & ($n - 1)" do?

Community
  • 1
  • 1
sarnold
  • 102,305
  • 22
  • 181
  • 238
1

It's a bitwise operation between a number and its previous number. Only way this expression could ever be false is if n is a power of 2, so essentially you're verifying if it isn't a power of 2.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
Neil
  • 5,762
  • 24
  • 36