bit test

[sjoemelfreek]

Hey there!

I tried this test and the values that I got where indeed the power of two.

I still don't understand the code though...

Could someone shed some light on this?

[tails]

The expression (x & (x - 1)) makes the last standing bit lie down. (I don't know how to say that in English. It is said 1 is standing and 0 is lying in Japanese.)

So, if the result is zero, x has at most only one standing bit in it, which means x is a power of two.

You'll find more of these hacks in Bit Twiddling Hacks.

[sjoemelfreek]

thanks, but I don't get it... It would be better if this challenge remained unsolved because I'm not worthy of solving it (yet)...

I guess I'll have to study it then...

[skragglies]

I spent like an hour trying to figure out the wording. I got it right away, since I've seen that snippet many times. I tried multiple of two, and then divisible by two - i know not a blank of blank. Then obviously I got it right. It's the only challenge that I instantly knew the answer to, and I almost fell out of my chair when I got it wrong the first time.

[MerickOWA]

thanks, but I don't get it... It would be better if this challenge remained unsolved because I'm not worthy of solving it (yet)...

I guess I'll have to study it then...

If you just consider the expression x & y == 0. This expression means that there are no bits that are 1 in both x & y. Since the expression in the challenge is x & (x-1) == 0, we need to consider how can subtracting 1 change all of x's bits that are 1 to zero so that when its then AND'd by its original value, you get zero as the result.

The simplest case to start with is x = 1. Obviously subtract one removes the only non-zero bit from x making it '0' and thus 1 & 0 == 0.

The general idea of subtracting one is that you start at the least significant bit. If that bit is zero, you move up to the next significant bit. Repeating until you find a bit that is set to '1'. At which point this bit becomes zero and all bits between this bit and the least significant bit (the string of zeros) becomes a string of ones.

Example 13184 - 1 = 11001110000000 - 1 = 11001101111111

See how the 7 zeros turn into 7 ones. and the 8th bit goes from a 1 to a zero. The rest of the bits remain unchanged. What does this mean?

Given that we want the AND'd result to be zero. All the bits set to 1 in 'x' must become zero.

We've already seen that when we subtract one from x, only a single bit changes from one to zero, the first non-zero bit or the least significant non-zero bit. If there is any other non-zero bits after the first one, subtracting 1 from x wont change them and thus the AND'd result WONT be zero.

Thus, x may only have one bit that is non-zero.
This makes it easy now to determine all numbers which satisfy the expression. The numbers in binary will be

1 = 1
2 = 10
4 = 100
8 = 1000
16 = 10000
etc...

at this point, maybe now its clearer why when "x & (x-1) == 0" is true, x must be a "power of two".

[sjoemelfreek]

I get it now.

Thank you for your effort!

[alx]

Hi,

that's great hacking code. I didn't saw it before and it took me some minutes of flipping bits in my brain to solve it for positive x.

But I'm still wondering why the parameter is 'int x' and not 'unsigned int x'. For negative numbers (and even x==0) things will become much more complicated and depending on the representation of negative numbers on the platform.

So to make it clearer the parameter should be unsigned und speacial treatment for x == 0 should be added.

[MerickOWA]

I'm not sure I've seen a platform yet that uses a one's complement to represent negative numbers. This makes adding and subtracting needlessly inefficient for the benefit? of a every so slightly faster negation operator (which really just becomes a duplicate not operator).

I think the assumption that negation is a two's complicate is a pretty safe assumption.

As for the unsigned vs signed, the only thing this would change is the last possible power of 2, 2^31 (or 2^15, 2^63 depending on the size of int). Technically this is a negative number and can't be represented by an int which only goes up to 2^31-1. The bit logical will still say that -2147483648 is a power of two.

Again, It doesn't change things a great deal, maybe just makes the code every so slightly more correct in one case (which is probably not one you'd be calling it on anyways) and probably gives you many compiler warnings in your code about signed vs unsigned conversions.

[megabreit]

Those text questions are very hard for non native speakers!
I hope there are not many of them.

I figured out real fast, that this function will check for even or odd input.
But to find the wanted wording caused me some headaches.

[aurora]

this was very funny. it was easy to figure out, what the function does and i'm sure i read the required answer hundreds of times the last years. but as i am not a native english speaker, i was not able to remember this words, for a few days.

now today i read some article about bit-operations in mysql and when i read through the article and stumbled over the phrase, i immediatly knew: that was the answer for this particular challange.

the funny thing is -- in my opinion -- even for a non native english speaker, it should not be that hard to figure out the required phrase -- especially not, when he is a developer (or hacker )

@tails: thanks for the "bit twiddling hacks" link btw. -- very interesting read!

[Aldreyu]

i had no idea, that this mathemaical 'function?' called 'power of x' in english...
but i knew the java method Math.pow(), so i had a look to the JavaDoc and then i had the answer...
Not easy for non-english speaker i think... but i solved id, so i'm happy...

(hope you can understand my english posts )

[rain1024]

Here's my hint:
a & b is and bit operator

Ex1: 3 & 2 = 11 & 10 = (1&1)(1&0) = 10 not equal 0
Ex1: 4 & 3 = 100 & 011 = (1&0)(0&1)(0&1) = 0

Hope that it will someone.

[compudemon]

i recognized the code snippet from java source code for the random numbers

[Limberneck]

The worst part of this was the wording of the answer. God damnit