August 12, 2010
The subject came up yesterday about counting bits. I remembered the subject from university in the context of error checking, but I couldn’t remember the specifics during the conversation. It was only later that I recalled the subject of Hamming values or weights, and from there I tracked down an algorithm by Brian Kernighan (or Peter Wegner, or Derrick Lehmer). For fun, I translated the C source to Python to yield the following:
def bit_count( v ): c = 0 while v > 0: v &= v - 1 c += 1 return c
For a bit of practice, I then opted to convert into Erlang:
bitcount(V) -> bitcount(V, 0). bitcount(0, C) -> C; bitcount(V, C) -> bitcount( (V band (V - 1)), (C + 1)).
I could probably roll the two arity 2 clauses into one, but this is a minor habit from my old Prolog days and I always feel it looks a bit cleaner than opting for a case statement. Feel free to disagree.
Since Clojure is my “language for 2010″, and I’ve been rather slack on keeping up with it lately:
(defn bit-count ([v] (bit-count v 0) ) ([v c] (if (zero? v) c (recur (bit-and v (dec v)) (inc c)))))
This feels like it could be expressed more functionally, dropping the two argument version for a compact one-argument version. This might be an interesting exercise for when I have a spare moment, unless someone out there already has a solution?
Just thought I’d share….