Just by accident I ran into the following funny comment:
98 /*
99 * Count the number of '1' bits in a word.
100 *
101 * Having completed this, I'm ready for an interview at Google.
102 *
103 * TODO? there's a parallel version w/o loops. Performance not currently
104 * important.
105 */
106 static int countOnes(u4 val)
107 {
108 int count = 0;
110 while (val != 0) {
111 val &= val-1;
112 count++;
113 }
115 return count;
116 }
:)
5 comments:
BTW: just a pointer to stackoverflow.com which really starts to get usefull:
http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer
It's the B. Kernighan method... Pretty standard. You can also use two other methods.
http://www.keil.com/support/docs/194.htm
The mask & shift method, or the index into an array. Just adjust for Word sized values from bytes.
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.
Hey! That's the code I sent to Google as part of the interview process! WTF?!
Wow… Finally I got the website for which I am searching for such a long time… I found my favorite
http://mobiappmax.com/
Post a Comment