What does the bitwise code "$n & ($n - 1)" do?

What does this code mean and what are oth开发者_运维问答er ways accomplish the same without using bit shifting?

if ($n & ($n - 1))

That formula checks to see whether a number is a power of 2 (if your condition as written is true, then the number is not a power of two).

Stated another way, your test checks to see whether there is more than one "1" bit set in the binary representation of $n. If there is zero or only one bit set, then your test will be false.

It is by far the most efficient way to determine that property.

First, this code is valid PHP, so your title is poor.

Second, the binary arithmetic going on looks something like this:

42 = 101010
   &
41 = 101001
-----------
40 = 101000

Like Greg states this is the fastest way to check for a power of 2 number, but the code you've given checks to see if the number is not a power of 2. This can easily be ascertained by PHP's policy of: any non-null/non-zero value is true.

When we use ($n & ($n - 1)) then it converts $n & ($n-1) to its binary values and does binary AND operation. Example

  3 = 0011
  4 = 0100
  5 = 0101

  3 = 0011
       &
  4 = 0100
------------
       0

  4 = 0100
       &
  5 = 0101
-----------
       100

To check if given number is power of 2 or not we alway use formulae ($n & ($n - 1) == 0) which means ANDing of $n & $n-1 is equals to 0 or not.

Online AND Operation Calculator