commit e339343c9c698a887681771372ba6cc58a79c707
author Cosmin Cojocar <cosmin.cojocar@gmail.com> Sun Apr 18 18:25:06 2010 +0200
committer Cosmin Cojocar <cosmin.cojocar@gmail.com> Tue Apr 20 22:13:26 2010 +0200
tree 237302fed1f7a04f82776488cb922b66b55d2d56
parent b16b78db118036d7df2cf5705baa18f34bd42eec

Improve the implementation of countOnes function to use only 12 operations.

Change-Id: I01b62606a0c87b2937572f8cb7beafc956867353

dexdump/DexDump.c

diff --git a/dexdump/DexDump.c b/dexdump/DexDump.c
index 6fed7aa..ccb6e0a 100644
--- a/dexdump/DexDump.c
+++ b/dexdump/DexDump.c
@@ -225,20 +225,14 @@
 
 /*
  * Count the number of '1' bits in a word.
- *
- * Having completed this, I'm ready for an interview at Google.
- *
- * TODO? there's a parallel version w/o loops.  Performance not currently
- * important.
  */
 static int countOnes(u4 val)
 {
     int count = 0;
 
-    while (val != 0) {
-        val &= val-1;
-        count++;
-    }
+    val = val - ((val >> 1) & 0x55555555);
+    val = (val & 0x33333333) + ((val >> 2) & 0x33333333);
+    count = (((val + (val >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
 
     return count;
 }