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

### Like this:

Like Loading...

*Related*

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 ]).

Ack – wordpress ate my comprehension. ‘< > <= Binary' is the generator clause in that comprehension.

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

http://realtimecollisiondetection.net/blog/?p=78

Love the Erlang version Geoff, and thanks for the link AdisH.

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)))

Here’s how I’d write it in Clojure:

http://pastebin.com/9Vm4RHjQ

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))))

Cool – thanks for the Clojure versions. Much appreciated!

Short Clojure version: 😉

(defn bit-count [n] (.bitCount (bigint n)))

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

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