I want a one line code to check whether a given integer is of form 2i - 2j or NOT. (using bitwise operators)
I tried to do it but I don't seem to be getting the answer. Can anyone please help me with this? It's kinda urgent... :-|
Thanks.
A:
In binary, a power of two is a number of the form 100...0 (A 1 followed by x 0s, where x is the exponent)
Therefore, any binary number of the form 2i - 2j will be a string of 1s followed by a string of 0s.
Windows Calculator (in binary mode) is a great way to experiment with this.
SLaks
2010-01-14 17:47:47
I know that its's 1s followed by 0s. What I am not able to figure out is how to test that with bitwise operators.
missingfaktor
2010-01-14 17:55:49
A:
Let's take a look at this for a moment. If i=j, then the answer is checking to see if the integer is 0. Otherwise, the key is to see how often the bits toggle I think as what you want to see is if all the 1s are together as a group, collectively, as really the arithmetic here is quite simple. If the toggle is 2 then it is of that form.
JB King
2010-01-14 17:48:52
A:
Left shift until you get a 0, once u get a zero, u should not get 1 again
hype
2010-01-14 17:55:04
And my point was about "shift until" because that involves repeating a certain action until a certain condition is true and this is not possible to do in one line. Changing "right" to "left" makes no difference as such.
missingfaktor
2010-01-15 08:35:44
Thats why i said in my second comment that its my mistake, the solution i suggested is not a one liner.
hype
2010-01-15 08:38:21
+6
A:
As AndreyT says, the answer can be found in Hacker's Delight:
Use the following formula to turn off the rightmost contiguous string of 1-bits (e.g., 01011000 ⇒ 01000000):
((x | (x – 1)) + 1) & xThis may be used to see if a nonnegative integer is of the form 2j – 2k for some j ≥ k ≥ 0; apply the formula followed by a 0-test of the result.
(was debating whether to post this, as it's a homework question, but as AndreyT already mentioned it and it's easily Googlable, I figure it's more helpful to quote directly; I'll let the questioner deal with the ethical implications of accepting help on the homework, and I expect that if his answer depends on this, he will write up the explanation of how it works himself)
Brian Campbell
2010-01-14 17:57:21
+1
A:
A hint or two:
Other have pointed out that what you're looking for is a number that consists of a string of ones followed by a string of zeros.
If you flip all the bits in this, you'll get a string of 0's followed by a string of 1's. If you increment that, all the one bits will become zeros, and exactly one bit above those will become a one.
If you AND those last two together, you'll get zero.
Jerry Coffin
2010-01-14 18:20:50