aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMattias Andrée <maandree@operamail.com>2014-01-20 04:04:12 +0100
committerMattias Andrée <maandree@operamail.com>2014-01-20 04:04:12 +0100
commit874371ea3a5ca7a4366cbe54bf8b0a77bf31894b (patch)
treef419e1786a1f931a7050a9f9fd84a4f5307baf7b
parentadd conditional negation (diff)
downloadalgorithms-and-data-structures-874371ea3a5ca7a4366cbe54bf8b0a77bf31894b.tar.gz
algorithms-and-data-structures-874371ea3a5ca7a4366cbe54bf8b0a77bf31894b.tar.bz2
algorithms-and-data-structures-874371ea3a5ca7a4366cbe54bf8b0a77bf31894b.tar.xz
m + counting bits
Signed-off-by: Mattias Andrée <maandree@operamail.com>
-rw-r--r--src/algorithms/bits/Bits.java81
-rw-r--r--src/algorithms/bits/Powers.java2
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