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

Advertisements

12 thoughts on “Bit Counts in Python, Erlang and Clojure

  1. I think the idiomatic way to do this in erlang is to use a binary comprehension: bitcount(Binary) when is_binary(Binary) -> lists:sum([ Bit || <> <= Binary ]).

      1. Using curly braces instead of angle brackets to keep wordpress happy – ‘{{ Bit:1 }} <= Binary'.

  2. If you’ve got a fixed size int, you can count bits in parallel. Here’s a clojure version for 64-bit ints:

    (defn BitCount [n]
    (let [count (- n
    (bit-and (bit-shift-right n 1) 0x7777777777777777)
    (bit-and (bit-shift-right n 2) 0x3333333333333333)
    (bit-and (bit-shift-right n 3) 0x1111111111111111))]
    (rem (bit-and (+ count (bit-shift-right count 4)) 0x0F0F0F0F0F0F0F0F) 255)))

  3. I think this is a more idiomatic (seq-oriented) Clojure version

    (defn bit-count [n]
    (count
    (take-while
    #(not (zero? %))
    (iterate #(bit-and % (dec %)) n))))

  4. -module(bitpop).
    -export([count/1]).

    count(X) when is_integer(X), X > 0 ->
    M1 = 16#5555555555555555, %% 0101…
    M2 = 16#3333333333333333, %% 00110011..
    M4 = 16#0f0f0f0f0f0f0f0f, %% 4 zeros, 4 ones …
    H01 = 16#0101010101010101, %% the sum of 256 to the power of 0,1,2,3…

    %% 1. put count of each 2 bits into those 2 bits
    X1 = X – (X bsr 1) band M1,
    %% 2. put count of each 4 bits into those 4 bits
    X2 = (X1 band M2) + ((X1 bsr 2) band M2),
    %% 3. put count of each 8 bits into those 8 bits
    X3 = (X2 + (X2 bsr 4)) band M4,
    %% 4. returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + …
    (X3 * H01) bsr 56.

    1. %% Fixed my earlier comment (doh! sorry…)
      -module(bitpop).
      -export([count/1]).

      count(0) -> 0;
      count(X)
      when is_integer(X), X > 0, X
      ((c4(X) bsr 16) + c4(X)) band 16#0000FFFF.
      c1(V) -> V – ((V bsr 1) band 16#55555555).
      c2(V) -> ((c1(V) bsr 2) band 16#33333333) + (c1(V) band 16#33333333).
      c3(V) -> ((c2(V) bsr 4) + c2(V)) band 16#0F0F0F0F.
      c4(V) -> ((c3(V) bsr 8) + c3(V)) band 16#00FF00FF.

      -ifdef(TEST).

      bitpop_test_() ->
      [?_assertEqual(0, count(0)),
      ?_assertEqual(1, count(1)),
      ?_assertEqual(2, count(3)),
      ?_assertEqual(3, count(7)),
      ?_assertEqual(4, count(15)),
      ?_assertEqual(5, count(31)),
      ?_assertEqual(6, count(63)),
      ?_assertEqual(7, count(127)),
      ?_assertEqual(8, count(255)),
      ?_assertEqual(1, count(4)),
      ?_assertEqual(1, count(8)),
      ?_assertEqual(1, count(16)),
      ?_assertEqual(1, count(32)),
      ?_assertEqual(1, count(64)),
      ?_assertEqual(1, count(128)),
      ?_assertEqual(1, count(256)),
      ?_assertEqual(1, count(512)),
      ?_assertEqual(1, count(1024)),
      ?_assertEqual(1, count(2048)),
      ?_assertEqual(1, count(16#FFFF + 1)),
      ?_assertEqual(19, count(16#FFFFE)),
      ?_assertEqual(1, count(16#FFFFF + 1)),
      ?_assertEqual(23, count(16#FFFFFE)),
      ?_assertEqual(1, count(16#FFFFF + 1)),
      ?_assertEqual(27, count(16#FFFFFFE)),
      ?_assertEqual(1, count(16#FFFFF + 1)),
      ?_assertEqual(31, count(16#FFFFFFFE)),
      ?_assertException(error, function_clause, count(-1))].

      -endif.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s