The bit logics; this two digits 1 and 0 can cause chaos

Are you a typical programmer who appreciates a diferent way of doing something? then you will definitely like this blogpost. After several months of thinking in terms of objects, believe me, it will be so difficult for anyone to come down to a level of thinking in terms bits. Cant believe it? then try to solve the following three programming puzzles.

Q1. Quickly find if a given number is a power of two or not?
Q2. Write logic to count the number of ones in a 32 bit unsigned integer? and finally
Q3. I have an array of numbers out of which all the numbers are occuring even number of times except for one that occurs odd number of times. Write a logic to find this number that is appearing odd number of times in the array?

If you have solved them without using bit level operations, thats fine, now try to solve them using bit level logic.

The Answers.
Ans1. If a number is a power of two then only one bit is 'on' in the bit representation of the number. Example int 2 is represented in binary as 0010, integer 4 is 0100, integer 8 is 1000. All the time if a number is a power of two there is only one 1 bit in the bit representation of the number. Now what? Try to make use of this property to find if a number is a power of two. Here we go.
If the number is n and if we do a logical and with (n-1) then all the bits should cancel out. so if n &(n-1) == 0 then the number is a power of two.

Ans2. After understanding this logic I now really have a tough time to explain it. Think on this. If I do something like this, what will happen?
n = n&(n-1);
if the number is 11. and we do n&(n-1) ie (1011) & (1010) n becomes (1010). making the last one bit in the bit representation of n, disappear. Now n =10 ie (1010) and now if we do n&(n-1) again then the last one bit in n will again disappear. Thus the algorithm goes as follows

unsigned count_ones(unsigned num){

unsigned count = 0;

while (num)
{
num &= num - 1;
++count;
}

return count;
}
Spend some time on it you will understand.

Ans3. This is a tricky question too. You should be knowing what xor does?
1 ^ 1 is 0
1 ^ 0 is 1
0 ^ 1 is 1
0 ^ 0 is 0
whats with this? If you xor a number with itself we get zero right? and if we agian xor zero with the number we get back the number. That means if we xor a number the even number of times then the result is zero and if we xor the number odd number of times the result is the number itself. eg x = 7 ^ 7 ^ 7 implies x is 7.

Now take an array of some numbers 2,5,6,2,5,5,6 if we keep on xoring the numbers ie 2 ^ 5 ^ 6 ^ 2 ^ 5 ^ 5 ^ 6 in this series of xoring the numbers that are appearing even number of times will cancel out to zero and the only number that is appearing odd number of times will be the result of the operation of xoring the whole array. we got the number, we wanted.

Enjoyed it, now if you are of the opinion that such answers cannot be expected of a candidate in an interview, then Iam with you. I agree that it is very rare that such a logic will strike your mind in the interview. Most of the times one can answer the question only if he/she read about the logic somewhere.