diff options
author | Mattias Andrée <maandree@operamail.com> | 2014-01-20 05:59:23 +0100 |
---|---|---|
committer | Mattias Andrée <maandree@operamail.com> | 2014-01-20 05:59:23 +0100 |
commit | 698a1bd8abf7739a983df66c01f0e3669f92d15c (patch) | |
tree | 70a0a4ddee5ec92f734b393e607f464e8c7c5360 /src/algorithms/bits | |
parent | more bit counting (diff) | |
download | algorithms-and-data-structures-698a1bd8abf7739a983df66c01f0e3669f92d15c.tar.gz algorithms-and-data-structures-698a1bd8abf7739a983df66c01f0e3669f92d15c.tar.bz2 algorithms-and-data-structures-698a1bd8abf7739a983df66c01f0e3669f92d15c.tar.xz |
add hybrid version of sideways addition
Signed-off-by: Mattias Andrée <maandree@operamail.com>
Diffstat (limited to '')
-rw-r--r-- | src/algorithms/bits/Bits.java | 21 |
1 files changed, 21 insertions, 0 deletions
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 } |