25,161
edits
Changes
Created page with "'''Home * People * Kim Walisch''' '''Kim Walisch''',<br/> a software engineer from Luxembourg, and avocational expert in [https://en.wikipedia.org/wiki/Prim..."
'''[[Main Page|Home]] * [[People]] * Kim Walisch'''
'''Kim Walisch''',<br/>
a software engineer from Luxembourg, and avocational expert in [https://en.wikipedia.org/wiki/Prime_number prime number] generation <ref>[http://www.primzahlen.de/referenten/Kim_Walisch/index2.htm Referent Kim Walisch www.primzahlen.de] (German)</ref> <ref>[https://en.wikipedia.org/wiki/Formula_for_primes Formula for primes from Wikipedia]</ref>, applying the [https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Sieve of Eratosthenes] <ref>[https://github.com/kimwalisch/primesieve GitHub - kimwalisch/primesieve: Fast C/C++ prime number generator]</ref>. He is knowledgeable about processor architectures, [[Optimization|software optimization]] and [[Bit-Twiddling|bit-twiddling]].
=Bitscan=
In October 2012, Kim Walisch proposed an improved [[BitScan#KimWalisch|bitscan routine]], multiplying the [[De Bruijn Sequence]] with a 0-1 mask [[General Setwise Operations#LS1BSeparation|separated]] by the [[General Setwise Operations#TheLeastSignificantOneBitLS1B|least significant one bit]] of a scanned integer or [[Bitboards|bitboard]]. The mask separation is cheaper than the [[General Setwise Operations#LS1BIsolation|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:
<pre>
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];
}
</pre>
<span id="PopCount"></span>
=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]], [http://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=
* [http://www.primzahlen.de/referenten/Kim_Walisch/index2.htm Referent Kim Walisch www.primzahlen.de] (German)
* [https://github.com/kimwalisch kimwalisch (Kim Walisch) · GitHub]
: [https://github.com/kimwalisch/libpopcnt GitHub - kimwalisch/libpopcnt: Fast C/C++ bit population count library] by [[Kim Walisch]]
=References=
<references />
'''[[People|Up one level]]'''
[[Category:Programmer]]
'''Kim Walisch''',<br/>
a software engineer from Luxembourg, and avocational expert in [https://en.wikipedia.org/wiki/Prime_number prime number] generation <ref>[http://www.primzahlen.de/referenten/Kim_Walisch/index2.htm Referent Kim Walisch www.primzahlen.de] (German)</ref> <ref>[https://en.wikipedia.org/wiki/Formula_for_primes Formula for primes from Wikipedia]</ref>, applying the [https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Sieve of Eratosthenes] <ref>[https://github.com/kimwalisch/primesieve GitHub - kimwalisch/primesieve: Fast C/C++ prime number generator]</ref>. He is knowledgeable about processor architectures, [[Optimization|software optimization]] and [[Bit-Twiddling|bit-twiddling]].
=Bitscan=
In October 2012, Kim Walisch proposed an improved [[BitScan#KimWalisch|bitscan routine]], multiplying the [[De Bruijn Sequence]] with a 0-1 mask [[General Setwise Operations#LS1BSeparation|separated]] by the [[General Setwise Operations#TheLeastSignificantOneBitLS1B|least significant one bit]] of a scanned integer or [[Bitboards|bitboard]]. The mask separation is cheaper than the [[General Setwise Operations#LS1BIsolation|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:
<pre>
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];
}
</pre>
<span id="PopCount"></span>
=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]], [http://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=
* [http://www.primzahlen.de/referenten/Kim_Walisch/index2.htm Referent Kim Walisch www.primzahlen.de] (German)
* [https://github.com/kimwalisch kimwalisch (Kim Walisch) · GitHub]
: [https://github.com/kimwalisch/libpopcnt GitHub - kimwalisch/libpopcnt: Fast C/C++ bit population count library] by [[Kim Walisch]]
=References=
<references />
'''[[People|Up one level]]'''
[[Category:Programmer]]
