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

Question

What does this code mean and what are other ways accomplish the same without using bit shifting?

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

Lottielotto

That's actually a bitwise-and, not a bit shift. – Rawdin

Why would you need to avoid bitwise operations this? – Ceballos

Because I don't understand them very well and a similar case might help me understand it better. And this is not homework. =) – Lottielotto

Answer 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.

Confidence

Greg, the question is, essentially, an adaptation that tests to see if a number isn't a power of two. Without == 0 PHP takes any non-zero value as true. – Cranach

Yes, I thought the logical negation would be clear. Nevertheless, I have amended my answer to make that explicit. – Confidence

Well, it isn't negation at first glance (that would be != 0), and my impression of eyze is that he's on a beginner's level. – Cranach

that's clever, i haven't seen this trick before. i had to do some math in my head to validate that this would work. :) – Dimitri

It's one of those "Old C Hacker's Tricks", except it should be $n ^ ($n-1), and it's used to find the smallest '1' bit of n. As it is written, it'll group 0 with all of your powers of two. Of course, my version will show '0' as being full of ones - but then, having more than one '1' could be seen as a useful way to show that there wasn't any '1' in the original number. I hope this helps. – Handed

Just to make thing a little clearer, the '^' sign in the formula above is supposed to be the eXclusive-OR (XOR) sign, which if you don't know it, is like a one-bit version of "!=" – Handed

Answer 2

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.

Cranach

Answer 3

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

Cornstarch