What does this code mean and what are other ways accomplish the same without using bit shifting?
if ($n & ($n - 1))
+15
A:
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.
Greg Hewgill
2009-10-11 19:20:56
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.
The Wicked Flea
2009-10-11 19:27:56
Yes, I thought the logical negation would be clear. Nevertheless, I have amended my answer to make that explicit.
Greg Hewgill
2009-10-11 19:29:02
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.
The Wicked Flea
2009-10-11 19:34:21
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. :)
Kip
2009-10-11 20:09:19
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.
BMeph
2010-07-01 19:13:02
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 "!="
BMeph
2010-07-01 19:14:47
+4
A:
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.
The Wicked Flea
2009-10-11 19:24:27