Difference between revisions of "Kim Walisch"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
Line 28: | Line 28: | ||
<span id="PopCount"></span> | <span id="PopCount"></span> | ||
=Population Count= | =Population Count= | ||
− | Kim Walisch provides a header-only [[C]]/[[Cpp|C++]] library for [[Population Count|counting the number of 1 bits]] using specialized instructions of various processor architectures <ref>[https://github.com/kimwalisch/libpopcnt GitHub - kimwalisch/libpopcnt: Fast C/C++ bit population count library]</ref>, performing algorithms as described by [[Wojciech Muła]] et al. <ref>[[Wojciech Muła]], [ | + | Kim Walisch provides a header-only [[C]]/[[Cpp|C++]] library for [[Population Count|counting the number of 1 bits]] using specialized instructions of various processor architectures <ref>[https://github.com/kimwalisch/libpopcnt GitHub - kimwalisch/libpopcnt: Fast C/C++ bit population count library]</ref>, performing algorithms as described by [[Wojciech Muła]] et al. <ref>[[Wojciech Muła]], [https://dblp.uni-trier.de/pers/hd/k/Kurz:Nathan Nathan Kurz], [https://github.com/lemire Daniel Lemire] ('''2016'''). ''Faster Population Counts Using AVX2 Instructions''. [https://arxiv.org/abs/1611.07612 arXiv:1611.07612]</ref>. |
=External Links= | =External Links= |
Latest revision as of 19:54, 27 August 2019
Kim Walisch,
a software engineer from Luxembourg, and avocational expert in prime number generation [1] [2], applying the Sieve of Eratosthenes [3]. He is knowledgeable about processor architectures, software optimization and bit-twiddling.
Bitscan
In October 2012, Kim Walisch proposed an improved bitscan routine, multiplying the De Bruijn Sequence with a 0-1 mask separated by the least significant one bit of a scanned integer or bitboard. The mask separation is cheaper than the bit isolation due to the x86 lea instruction, performing the decrement of a source register into another target register, not affecting processor flags. This is a 32-bit bitscan forward routine:
const int index32[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; /** * bitScanForward * @author Kim Walisch (2012) * @param v 32-bit set * @precondition v != 0 * @return index (0..31) of least significant one bit */ int bitScanForward(unsigned int v) { return index32[((v ^ (v - 1)) * 0x07C4ACDDU) >> 27]; }
Population Count
Kim Walisch provides a header-only C/C++ library for counting the number of 1 bits using specialized instructions of various processor architectures [4], performing algorithms as described by Wojciech Muła et al. [5].
External Links
References
- ↑ Referent Kim Walisch www.primzahlen.de (German)
- ↑ Formula for primes from Wikipedia
- ↑ GitHub - kimwalisch/primesieve: Fast C/C++ prime number generator
- ↑ GitHub - kimwalisch/libpopcnt: Fast C/C++ bit population count library
- ↑ Wojciech Muła, Nathan Kurz, Daniel Lemire (2016). Faster Population Counts Using AVX2 Instructions. arXiv:1611.07612