techInterview Discussion

A part of answers to technical interview questions.

Your host: Michael Pryor

problems using bit operators


Can anyone PLEASE suggest some book or online resources where you can find problems in C involving bit operators?
For eg find if a number is a power of 2.

I REALLY NEED to practice some problems involving bit level operators.

Big thanks in advance!!!!
Thursday, March 16, 2006
If a # is a power of 2, it's binary number will have exactly one "1" in it (except the first bit, which is 1, 2 to the power of zero).

<< shift bit to the left
>> shift bit to the right
& bitwise AND
| bitwise OR

One thing about bit counting is that if you keep bitwise-and'ing with a number 1 less than the result you can get the # of bits set.

E.g. how many bits in int 7.

7 = 111 in binary.
count = 0.

111 - 1 = 110
111 & 110 = 110 (1)

110 - 1 = 101
110 & 101 = 100 (2)

100 - 1 = 099
100 & 099 = 000 (3)

result is 3.

code is like:
int num = 0;
int n = 7;
while (n>0) {
  n &= n-1;
nicky Send private email
Friday, March 17, 2006
hi nicky,

Thanks for the solution. But that was just an example to suggest what kind of problems I'm looking for.
I knw the solution to that problem. :)

anyway thanks for replying....

please someone tell me online resources or books where I can find more problems on bit operators....OR if someone has a collection of such problems can you please post it here?

Thanks a TON in advance....
Friday, March 17, 2006
Maybe the book Hacker's Delight is what you want.
Friday, March 17, 2006
There is an o(1) solution to this! (This the advantages of being with really smart people in College!!). As already stated there is exactly one '1' followed by lets say, 'n-1' zero's in any power of two where 2^n is the number we're looking at. Therefore n-1 whould have exactly n-1 ones. Now And These two and you';; get 0!!

like in
n = 8 = 1000
n-1 = 7 = 111

n&(n-1) == 0
Rave Hanker Send private email
Friday, March 17, 2006
Hacker's Delight is a good one!

check some other books at
bekz Send private email
Saturday, March 18, 2006
A bit late to the party, but here's a neat link:
Saturday, March 25, 2006
awesome link.
Thanks Tom
Saturday, March 25, 2006

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz