IntBitfield: Add bit-count, O(1) per int-element, using HAKEM.

1 files changed, 26 insertions, 0 deletions

diff --git a/src/java/com/jogamp/common/util/IntBitfield.java b/src/java/com/jogamp/common/util/IntBitfield.java
index 6b277e0..ad27dff 100644
--- a/src/java/com/jogamp/common/util/IntBitfield.java
+++ b/src/java/com/jogamp/common/util/IntBitfield.java
@@ -136,4 +136,30 @@ public class IntBitfield {
         }
         return prev;
     }
+    /**
+     * Returns the number of set bits within given 32bit integer in O(1)
+     * using <i>HAKEM Bit Count</i>:
+     * <pre>
+     *   http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
+     *   http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item169
+     *   http://tekpool.wordpress.com/category/bit-count/
+     * </pre>
+     */
+    public static final int getBitCount(final int n) {
+        int c = n;
+        c -= (n >> 1) & 033333333333;
+        c -= (n >> 2) & 011111111111;
+        return ( (c + ( c >> 3 ) ) & 030707070707 ) % 63;
+    }
+    
+    /** 
+     * Returns the number of set bits within this bitfield.
+     */
+    public long getBitCount() {
+        long c = 0;
+        for(int i = storage.length-1; i>=0; i--) {
+            c += getBitCount(storage[i]);
+        }
+        return c;
+    }
 }