Skip to content

Instantly share code, notes, and snippets.

@gburd
Last active July 2, 2018 06:27
Show Gist options
  • Save gburd/4955104 to your computer and use it in GitHub Desktop.
Save gburd/4955104 to your computer and use it in GitHub Desktop.
Hamming weight of 64bit integers in Erlang using the popcount_3() method found http://en.wikipedia.org/wiki/Hamming_weight counts the number of bits set to 1.
%% -*- coding: utf-8 -*-
%%
%% %CopyrightBegin%
%%
%% Copyright (C) 2013 Gregory Burd. All Rights Reserved.
%%
%% The contents of this file are subject to the Mozilla Public License,
%% Version 2, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Mozilla Public License along with this software. If not, it can be
%% retrieved online at http://www.mozilla.org/MPL/
%%
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
%%
%% %CopyrightEnd%
%%
-module(bitpop).
-ifdef(TEST).
-include_lib("eunit/include/eunit.hrl").
-endif.
-export([count/1]).
count(0) -> 0;
count(X)
when is_integer(X), X > 0, X < 16#FFFFFFFF ->
((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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment