popcnt - count bits set ("1") in a integer, of course using python
I've implemented only four ways to do this:
- using look up table 0..255 (no iterations, oen sum and a few shifting by 8 bits)
- naive (number of iterations == number of bits)
- Brian Kernighan way (number of iterations == number of bits set)
- pythonic by ugly (count "1"s after calling bin()...)
All function were run on 1000 samples made by 100 random numbers:
And now testing results:
[Wed, 05 Jun 22:07 E0][cibak@localhost:~/popcnt]> time python testNaive.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
175.885u 0.055s 2:56.35 99.7% 0+0k 0+0io 0pf+0w
[Wed, 05 Jun 22:04 E0][cibak@localhost:~/popcnt]> time python testBK.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
75.853u 0.028s 1:16.03 99.7% 0+0k 0+0io 0pf+0w
[Wed, 05 Jun 22:06 E0][cibak@localhost:~/popcnt]> time python testLUT.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
42.828u 0.030s 0:42.93 99.8% 0+0k 0+0io 0pf+0w
[Wed, 05 Jun 22:04 E1][cibak@localhost:~/popcnt]> time python testUgly.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
40.880u 0.040s 0:41.06 99.6% 0+0k 0+0io 0pf+0w
And guess what? Ugly (but pythonic) won! Coincidence? I don't think so... ;)
EDIT:
And of course I can completely remove lines with lambda and all this stuff within popcntLUT and it could be coded just like that:
But it doesn't help to much.
Also one can check say 16 bits look up table, say:
This should run at least 2 times faster that original popcntLUT.