m + counting bits

Signed-off-by: Mattias Andrée <maandree@operamail.com>

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