From 698a1bd8abf7739a983df66c01f0e3669f92d15c Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Mon, 20 Jan 2014 05:59:23 +0100 Subject: add hybrid version of sideways addition MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/algorithms/bits/Bits.java | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) diff --git a/src/algorithms/bits/Bits.java b/src/algorithms/bits/Bits.java index abe156a..24ec464 100644 --- a/src/algorithms/bits/Bits.java +++ b/src/algorithms/bits/Bits.java @@ -220,6 +220,27 @@ public class Bits rc = (£{T})(((rc >> 32) + rc) & (£{T})0x00000000FFFFFFFFL); return rc; } + + /** + * Calculate the number of set bits in an integer, parallel–64bits-like hybrid version, probably the best version + * + * @param value The integer + * @return The number of set bits + */ + public static £{T} ones_hybrid(£{T} value) + { +£>L1="($T)$(bc <<< "(256^$S - 1) / 3")L" +£>L2="($T)$(bc <<< "(256^$S - 1) / 15 * 3")L" +£>L3="($T)$(bc <<< "(256^$S - 1) / 255 * 15")L" +£>L4="($T)$(bc <<< "(256^$S - 1) / 255")L" + + value -= (value >> 1) & £{L1}; + value = (£{T})((value & £{L2}) + ((value >> 2) & £{L2})); + value = (value + (value >> 4)) & £{L3}; + value = (value * £{L4}) >> (($S - 1) * 8); + return value; /* Only applicable upto 128 bits */ + } + £>done } -- cgit v1.2.3-70-g09d2