aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorSven Gothel <[email protected]>2013-04-11 06:49:24 +0200
committerSven Gothel <[email protected]>2013-04-11 06:49:24 +0200
commit21fc00af1c404d93280e21d05efc124ec23d575b (patch)
tree733dd44b8cacac0d1b05fddd8ccd0deb202dbd86
parent2df69c716ce55c7db58963d7cd04262aebcad572 (diff)
IntBitfield: Add bit-count, O(1) per int-element, using HAKEM.
-rw-r--r--src/java/com/jogamp/common/util/IntBitfield.java26
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;
+ }
}