Tuesday, October 21, 2008

Funny comment in the Android sources

Android is now open source.

Just by accident I ran into the following funny comment:

98 /*

99 * Count the number of '1' bits in a word.
101 * Having completed this, I'm ready for an interview at Google.

103 * TODO? there's a parallel version w/o loops. Performance not currently
104 * important.
105 */
106 static int countOnes(u4 val)

108 int count = 0;
110 while (val != 0) {

111 val &= val-1;
112 count++;

115 return count;



eckes said...

BTW: just a pointer to stackoverflow.com which really starts to get usefull:


Porter Woodward said...

It's the B. Kernighan method... Pretty standard. You can also use two other methods.


The mask & shift method, or the index into an array. Just adjust for Word sized values from bytes.

Markus Kohler said...

thanks for the comments.
Having a really good algorithm for counting the number of bits in an arbitrary large bitset could be actually useful for some of the algorithms in the Eclipse Memory Analyzer.

All those algorithms should be applicable of course. I think I need to check where we would really get a benefit.

Anonymous said...

Hey! That's the code I sent to Google as part of the interview process! WTF?!

ayyappa said...

Wow… Finally I got the website for which I am searching for such a long time… I found my favorite