Last active
July 2, 2018 06:27
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%% -*- 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