Module: Mesa Branch: master Commit: c93dcbfea7b8e1cd0f14a96bc466419bdce7eb30 URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=c93dcbfea7b8e1cd0f14a96bc466419bdce7eb30
Author: Corbin Simpson <[email protected]> Date: Sat Nov 28 10:13:51 2009 -0800 util: Improve bitcount. Sorry for not pushing this before, it got lost in stashes. --- src/gallium/auxiliary/util/u_math.h | 12 ++++++++---- 1 files changed, 8 insertions(+), 4 deletions(-) diff --git a/src/gallium/auxiliary/util/u_math.h b/src/gallium/auxiliary/util/u_math.h index 7e75702..c4faec6 100644 --- a/src/gallium/auxiliary/util/u_math.h +++ b/src/gallium/auxiliary/util/u_math.h @@ -499,11 +499,15 @@ util_bitcount(unsigned n) #if defined(PIPE_CC_GCC) return __builtin_popcount(n); #else - /* XXX there are more clever ways of doing this */ + /* K&R classic bitcount. + * + * For each iteration, clear the LSB from the bitfield. + * Requires only one iteration per set bit, instead of + * one iteration per bit less than highest set bit. + */ unsigned bits = 0; - while (n) { - bits += (n & 1); - n = n >> 1; + for (bits, n, bits++) { + n &= n - 1; } return bits; #endif _______________________________________________ mesa-commit mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/mesa-commit
