Bit-Level Operation Tricks

These days I am reading Computer Systems: A Programmer’s Perspective by R. Bryant and D. O’Hallaron, which is an extremely interesting and useful book. The first edition of this book was the textbook of one of my courses in the university, though I did not have the chance to read it carefully due to the lack of time (there were so many courses). Now I finally get the chance to read this wonderful book cover to cover.

While doing the Data Lab, I encountered several problems whose solutions are quite tricky. There are three of them: bitCount, bang and ilog2.

bitCount requires us to write a function returning count of number of 1's in a word using almost only bit-level operations !, ~, &, ^, |, +, << and >>. The answer is a classical application of parallel computation, computing the sums of every 2, 4, 8, 16 and finally 32 bits in the word.

bang is the most tricky one among these problems in my opinion. It asks us to compute !x without using !. The point of the solution is to use sign bit as the indicator: converting negative values to positive ones, then subtracting one from the number, giving a negative value for input 0 and non-negative number for any other inputs.

ilog2 requires us to implement floor(log₂x) using the same operations as we are allowed to use in bitCount. This problem is equivalent to find the position of the most significant bit of 1. A clever way to do it is using binary search, but we are forbidden to use any control constructs. In order to create branch, notice that the following code

x = ((~c + 1) & A) + (~(~c + 1) & B);

is equivalent to

if (c == 1) x = A;
else if (c == 0) x = B;
else /* I don't care */

Based on this we can use the binary search to find the answer.

By now I have just read the first two chapters of the book. I will upload the solutions (written by myself, certainly) when I finish all the labs (which might never come).