Bit Counts in Python, Erlang and Clojure

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….

About these ads