4 ms·
So… someone care to explain to me where I'm going egregiously wrong, apparently? Because, at least on my machine with the code I spewed out quickly, the Kerning
by Merovius 10y ago
So… someone care to explain to me where I'm going egregiously wrong, apparently? Because, at least on my machine with the code I spewed out quickly, the Kerningham way of counting bits is ~6x slower than a lookup table (including generating the table itself).
http://sprunge.us/IIEH http://sprunge.us/IIEH
The Kerningham way code seems faster for very sparse arrays (i.e. only one bit set per uint16), but slower otherwise.
- tjalfi 10y agoYou weren't doing anything wrong. He discusses two methods: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan https://graphics.stanford.edu/~seander/bithacks.html#CountBi... https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel https://graphics.stanford.edu/~seander/bithacks.html#CountBi... The second option will probably beat a byte lookup table. GCC switched from a lookup table to similar code. If this still isn't fast enough, try using SIMD registers and the Harley/Seal method based on carry save adders (http://www.hackersdelight.org/hdcodetxt/popArrayHS.c.txt http://www.hackersdelight.org/hdcodetxt/popArrayHS.c.txt). If you like this sort of bit twiddling, you probably would enjoy Henry Warren's Hacker's Delight.