Optimize bitcount32 by replacing 6 logical operations with 2. The key

observation here is that it doesn't matter what garbage accumulates in
bits which we're going to end up masking away anyway, as long as the
garbage doesn't overflow into bits which we care about.

This improved version may not be the fastest possible on all systems,
but it's certainly going to be better than what was here before.

1 files changed, 3 insertions, 3 deletions

diff --git a/sys/sys/systm.h b/sys/sys/systm.h
index e84bf1b..6fa2bfa 100644
--- a/sys/sys/systm.h
+++ b/sys/sys/systm.h
@@ -391,9 +391,9 @@ bitcount32(uint32_t x)
 
 	x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
 	x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
-	x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
-	x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
-	x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
+	x = (x + (x >> 4)) & 0x0f0f0f0f;
+	x = (x + (x >> 8));
+	x = (x + (x >> 16)) & 0x000000ff;
 	return (x);
 }