Kim Walisch

Edit 0 11 …
Home * People * Kim Walisch

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

  1. ^ Referent Kim Walisch www.primzahlen.de (German)
  2. ^ Formula for primes from Wikipedia
  3. ^ GitHub - kimwalisch/primesieve: Fast C/C++ prime number generator
  4. ^ GitHub - kimwalisch/libpopcnt: Fast C/C++ bit population count library
  5. ^ Wojciech Muła, Nathan Kurz, Daniel Lemire (2016). Faster Population Counts Using AVX2 Instructions. arXiv:1611.07612

What links here?

Page Date Edited
BitScan Sep 10, 2017
Hakkapeliitta Apr 26, 2016
Kim Walisch Aug 10, 2017
People Feb 28, 2018
Piece-Sets Jun 9, 2017
Population Count Sep 3, 2017
Tunguska Sep 16, 2017
Wojciech Muła Aug 10, 2017

Up one level