diff options
| -rw-r--r-- | src/algorithms/bits/Bits.java | 81 | ||||
| -rw-r--r-- | src/algorithms/bits/Powers.java | 2 |
2 files changed, 81 insertions, 2 deletions
diff --git a/src/algorithms/bits/Bits.java b/src/algorithms/bits/Bits.java index 4a08d05..0930b19 100644 --- a/src/algorithms/bits/Bits.java +++ b/src/algorithms/bits/Bits.java @@ -22,7 +22,32 @@ package algorithms.bits; */ public class Bits { -£>for T in char byte short int long; do +£<function table + { + if [ $1 = 0 ]; then + echo -n "${2}, " + else + level=$(( $1 - 1 )) + table $level $(( $2 + 0 )) + table $level $(( $2 + 1 )) + table $level $(( $2 + 1 )) + table $level $(( $2 + 2 )) + fi +£>} + + /** + * Lookup table for the number of set bits in a byte + */ + private static byte[] ONES_TABLE_256 = { £(table 4 0) }; + /* ONES_TABLE_256[0] = 0; + * for (int i = 0; i < 256; i++) + * ONES_TABLE_256[i] = (i & 1) + ONES_TABLE_256[i / 2]; + */ + + +£<for T_S in char_2 byte_1 short_2 int_4 long_8; do + T=${T_S%_*} +£>S=${T_S#*_} /** * Sets or clears individual bits in an integer * @@ -61,6 +86,60 @@ public class Bits { return (£{T})(zero ^ ((£{T})(zero ^ one) & mask)); } + + /** + * Clears the least significant bit set + * + * @param value The integer + * @return The value with its least significant set bit cleared + */ + public static £{T} clearLeastSignificant(£{T} value) + { + return (£{T})(value & (value - 1)); + } + + /** + * Calculate the number of set bits in an integer, naïve version + * + * @param value The integer + * @return The number of set bits + */ + public static £{T} ones_naïve(£{T} value) + { + £{T} count = 0; + for (; value != 0; value >>>= 1) + count += (£{T})(value & 1); + return count; + } + + /** + * Calculate the number of set bits in an integer, Wegner's version + * + * @param value The integer + * @return The number of set bits + */ + public static £{T} ones_wegner(£{T} value) + { + £{T} count = 0; + for (; value != 0; count++) + value &= value - 1; /* clear the least significant bit set */ + return count; + } + + /** + * Calculate the number of set bits in an integer, partial lookup table version + * + * @param value The integer + * @return The number of set bits + */ + public static £{T} ones_table(£{T} value) + { +£<function lookup + { echo "ONES_TABLE_256[(int)((value >> $1) & 255)]" +£>} + return (£{T})((£{T})(£(lookup 0) + £(lookup 8)) + (£{T})(£(lookup 16) + £(lookup 24))); + /* In C you can split the value by getting the address of the value and cast the pointer to char* */ + } £>done } diff --git a/src/algorithms/bits/Powers.java b/src/algorithms/bits/Powers.java index df6f926..84c9399 100644 --- a/src/algorithms/bits/Powers.java +++ b/src/algorithms/bits/Powers.java @@ -32,7 +32,7 @@ public class Powers */ public static boolean isPowerOf2(£{T} value) { - return (value & (value - 1)) == 0; + return (value & (value - 1)) == 0; /* The left hand side clears the least significant bit set */ /* Or alternatively: (value & -value) == value */ } £>done |