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