techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

problems using bit operators

Hi,

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!!!!
codeislife
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;
  num++;
}
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....
codeislife
Friday, March 17, 2006
 
 
Maybe the book Hacker's Delight is what you want.
leisure
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 http://cprogrammers.blogspot.com/2005/11/programming-must-read-books.html
bekz Send private email
Saturday, March 18, 2006
 
 
A bit late to the party, but here's a neat link:

http://aggregate.org/MAGIC/
Tom_
Saturday, March 25, 2006
 
 
awesome link.
Thanks Tom
codeislife
Saturday, March 25, 2006
 
 

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

Other recent topics Other recent topics
 
Powered by FogBugz