Agilent Technologies Interview Question Software Engineer / Developers
It determines if n is a power of two. The "why it works" is a bit more interesting.
It's easy to show that it works for a power of two: take the value 16, for instance.
In binary, this is 10000. Now subtract 1 (15); in binary, this is 01111. Obviously, logically AND'ing these two values will produce 0, since they have no bits in common.
The really interesting question is: how can you prove that this rule (that n and n-1 will have no bits in common) only applies to powers of 2?
( (N&(N-1)) == 0 ) checks whether is N is a power of 2 or not.
Basic : ( 2^i + 2^j ) is not a power of two for any positive integer i and j.
Therefore if only one bit
is set then it's a power of 2 and vice-versa.
Consider the number N with K bits long.
If the LSB of N is 1, then obviously (N-1) will have LSB set to 0 without altering the other bits. Hence ( N & (N-1) ) will be 0 only if LSB is set, if it is non-zero then some other bits in N is also set. So if two or more bits are set then it's not a power of 2.
If LSB of N is 0, then from binary arithmetic :
( 0 - 1 )=1 with a carry 1
Suppose that i th position in N is the first bit set ( that means bit position 0 to (i-1) are all 0s ). So in ( N-1 ), all the bits from 0 to i-1 are 1 and i th position is 0. So if any other bit position from (i+1) to K is set, then obviously ( N & (N - 1) ) will be non-zero. If no bit from (i+1) to K is set then ( N & (N-1) ) will be 0 and i th position is the only bit set in N.
Hope I was clear and did not confuse anybody.
Thanks
Thirumalai
That is a kewl one.
How about this one?
((n | (n - 1)) == ((n << 1) - 1)) . Scroll down for the ans. I came up with this one! Yeah, given the time and resources you can come up with your own puzzles.
It is always easy to analyze it and understand when you are relaxed and have all the time to experiment. But the question is how do you attack the problem when you are put on the spot and are under pressure. That is what separates the kewl person and the nervous pack. Unfortunately it is the harsh reality.
((n | (n - 1)) == ((n << 1) - 1)) is the same as ( (n & (n-1)) == 0)
i suppose that it will check for the anding condition if if statementif there in front of the statement
- anil February 12, 2006