Thursday, September 18, 2008

Fast Bit Counting Techniques


Devise a fast algorithm for counting the number of bits set in an unsigned integer.

Commonly asked in job interviews for Software Engineers. I first heard it in March 2008 when I was taking a Job Interview.

To really appreciate the power of these techniques, I suggest you copy the code and test them using your favorite C compiler.

Solution:

1) Traditional Method:

int bitcount (unsigned int n)
{
int count = 0;
while (n)
{
count += n & 0x1u;
n >>= 1;
}
return count;
}


Iterated Count runs in time proportional to the total number of bits. It simply loops through all the bits, terminating slightly earlier because of the while condition. Useful if 1’s are sparse and among the least significant bits.


2.1) Sparse Ones

int bitcount (unsigned int n)
{
int count = 0 ;
while (n)
{
count++ ;
n &= (n - 1) ;
}
return count ;
}

Sparse Ones runs in time proportional to the number of 1 bits. The mystical line n &= (n - 1) simply sets the rightmost 1 bit in n to 0.


2.2) Dense Ones

int bitcount (unsigned int n)
{
int count = 8 * sizeof(int) ;
n ^= (unsigned int) - 1 ;
while (n)
{
count-- ;
n &= (n - 1) ;
}
return count ;
}

Dense Ones runs in time proportional to the number of 0 bits. It is the same as Sparse Ones, except that it first toggles all bits (n ~= -1), and continually subtracts the number of 1 bits from sizeof(int).


3.1) Precompute_8bit

/* This array contains no of bits set in 0,1,2,3,4 ...255 */
int bits_in_char [256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

int bitcount (unsigned int n)
{
// works only for 32-bit ints
return bits_in_char [n & 0xffu]
+ bits_in_char [(n >> 8) & 0xffu]
+ bits_in_char [(n >> 16) & 0xffu]
+ bits_in_char [(n >> 24) & 0xffu] ;
}

Precompute_8bit assumes an array bits_in_char such that bits_in_char[i] contains the number of 1 bits in the binary representation for i. It repeatedly updates count by masking out the last eight bits in n, and indexing into bits_in_char.


3.2) Precompute_16bit

char bits_in_16bits [0x1u << 16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, ...} ;
int bitcount (unsigned int n)
{
// works only for 32-bit ints
return bits_in_16bits [n & 0xffffu]
+ bits_in_16bits [(n >> 16) & 0xffffu] ;
}

Precompute_16bit is a variant of Precompute_8bit in that an array bits_in_16bits[] stores the number of 1 bits in successive 16 bit numbers (shorts).

4) Parallel Count

#define TWO(c) (0x1u << (c))
#define MASK(c) (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
#define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))

int bitcount (unsigned int n)
{
n = COUNT(n, 0) ;
n = COUNT(n, 1) ;
n = COUNT(n, 2) ;
n = COUNT(n, 3) ;
n = COUNT(n, 4) ;
/* n = COUNT(n, 5) ; for 64-bit integers */
return n ;
}

Parallel Count carries out bit counting in a parallel fashion. Consider n after the first line has finished executing. Imagine splitting n into pairs of bits. Each pair contains the number of ones in those two bit positions in the original n. After the second line has finished executing, each nibble contains the number of ones in those four bits positions in the original n. Continuing this for five iterations, the 64 bits contain the number of ones among these sixty-four bit positions in the original n. That is what we wanted to compute.


5) Nifty Parallel Count

#define MASK_01010101 (((unsigned int)(-1))/3)
#define MASK_00110011 (((unsigned int)(-1))/5)
#define MASK_00001111 (((unsigned int)(-1))/17)
int bitcount (unsigned int n) {
n = (n &a MASK_01010101) + ((n >> 1) & MASK_01010101) ;
n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
return n % 255 ;
}

Nifty Parallel Count works the same way as Parallel Count for the first three iterations. At the end of the third line (just before the return), each byte of n contains the number of ones in those eight bit positions in the original n. A little thought then explains why the remainder modulo 255 works.


6) MIT HAKMEM Count for 32-bit Unsigned Integer

int bitcount32(unsigned int n)
{
/* works for 32-bit numbers only */
/* fix last line for 64-bit numbers */

register unsigned int tmp;

tmp = n - ((n >> 1) & 033333333333)
- ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}

MIT HAKMEM Count is funky. Consider a 3 bit number as being 4a+2b+c. If we shift it right 1 bit, we have 2a+b. Subtracting this from the original gives 2a+b+c. If we right-shift the original 3-bit number by two bits, we get a, and so with another subtraction we have a+b+c, which is the number of bits in the original number. How is this insight employed? The first assignment statement in the routine computes tmp. Consider the octal representation of tmp. Each digit in the octal representation is simply the number of 1’s in the corresponding three bit positions in n. The last return statement sums these octal digits to produce the final answer. The key idea is to add adjacent pairs of octal digits together and then compute the remainder modulus 63. This is accomplished by right-shifting tmp by three bits, adding it to tmp itself and ANDing with a suitable mask. This yields a number in which groups of six adjacent bits (starting from the LSB) contain the number of 1’s among those six positions in n. This number modulo 63 yields the final answer. For 64-bit numbers, we would have to add triples of octal digits and use modulus 1023.

7) MIT HAKMEM Count for 8-bit Unsigned Char

int bitcount8(unsigned char b)
{
b = (b & 0x55u) + ((b >> 1) & 0x55u);
b = (b & 0x33u) + ((b >> 2) & 0x33u);
b = (b & 0x0fu) + ((b >> 4) & 0x0fu);

return (b);
}


8) MIT HAKMEM Count for 64-bit Unsigned Integer

typedef unsigned __int64 uint64; //assume this gives 64-bits on windows
const uint64 m1 = 0x5555555555555555; //binary: 0101...
const uint64 m2 = 0x3333333333333333; //binary: 00110011..
const uint64 m4 = 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ...
const uint64 m8 = 0x00ff00ff00ff00ff; //binary: 8 zeros, 8 ones ...
const uint64 m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64 m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64 hff = 0xffffffffffffffff; //binary: all ones
const uint64 h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//It uses 24 arithmetic operations (shift, add, and).
int bitcount64(uint64 x) {
x = (x & m1 ) + ((x >> 1) & m1 ); //put count of each 2 bits into those 2 bits
x = (x & m2 ) + ((x >> 2) & m2 ); //put count of each 4 bits into those 4 bits
x = (x & m4 ) + ((x >> 4) & m4 ); //put count of each 8 bits into those 8 bits
x = (x & m8 ) + ((x >> 8) & m8 ); //put count of each 16 bits into those 16 bits
x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits
x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits
return (int)x;
}


If you are interested in more bit twiddling techniques, go through this site.
There are some lovely solutions for some common bit twiddling problems. http://graphics.stanford.edu/~seander/bithacks.html

Disclaimer: This article is not written by me, it is my collection from the internet over a period of time.

Wednesday, September 3, 2008

Google Chrome - The new web browser

I have downloaded the new Google Chrome web browser Beta release and used it for sometime. I love the browser's look and feel and its cool features. Here is my review of the new browser.

Pros:

1. Chrome's address bar box can also be used as the search box so you don't have to browse to a search engine to perform searches. This means, address bar is doubled as Google Toolbar, no need to have additional box for the Google Toolbar. This is called Omnibox feature, one box for both search and web address.

2. You can drag a tab from the browser to your desktop to create a new window, and likewise if you have an open window and want to embed one tab into another window, you can do so by dragging it in between the tabs you want it to reside in.

3. Chrome is designed using multiple processes for multiple tabs.. This means each of the browser's tabs run as their own isolated process, not thread — if one tab crashes, the other tabs will remain untouched.

4. The browser has simple interface without any toolbars, menus and other stuff. That is plain and simple.

5. When you install the Chrome browser, it will import bookmarks from an existing browser, these bookmarks are not intuitive to access from Chrome. But you can press Ctrl+B to get the bookmarks bar, or on the right most corner of the browser, click on "Customize and Control Google Chrome" and then select "Always Show Bookmarks Bar".

6. One of Google Chrome’s nifty feature is its incognito mode which basically wipes all traces of web browsing activity after closing the incognito session. As a by-product, you can actually use incognito mode to log in simultaneously to two separate accounts like Gmail for instance if you are logged in on the regular browsing mode as well. Since the cookies between regular and incognito browsing modes are maintained separately, you will be able to be logged in under two different accounts to pretty much any website you have an account on. Log in once normally, log in again with a different account but going incognito. Imagine the endless possibilities, like chatting with yourself on Google Talk, Yahoo messenger!

7. You can nicely arrange your bookmarks on bookmarks bar, so that on a single click you can open all your frequent web sites.

8. The big nuisance pop-ups won't trouble you as much as they do on other browsers. Chrome has a nice way of placing these pop-up on the status bar, virtually making it no nonsense stuff, I like the Google's treatment to the annoying pop-ups problem.

9. You can see and go back directly to any page in the history by clicking and holding on the back icon.

Cons:

1. If you have multiple tabs open, and you try to close the window, it will silently close all tabs, it won't prompt you like Firefox, and IE that multiple tabs are open.

2. Until now there are not many third party plugins available, firefox is a clear leader in this category.

3. Language support is not extensive, you can not browse many different language sites as you can with IE and Firefox.