Here are some bit manipulation identities that can be helpful to writing efficient code. In the below, we assume variables are 32 or 64-bit integers. Think C code.
Primitives used are integer arithmetic (+, -, *, /) and logical bitwise operations (&, |, ^, ~), and logical shift (<<, >>).
lzcnt computes the number of leading zeros, tzcnt computes the number of trailing zeros. pdep(p,m) deposits the bits of p onto the non-zero positions of m. pext(p,m) extracts the bits from p indicated by a 1-bit in m into consecutive bit positions, filling as many as bits set in m.
bzhi(a,k) clears all but the least significant k bits in a.
See also SIMD Bit Twiddling Hacks
Operations on multiple lzcnt and tzcnt calls
- min( lzcnt( a ), lzcnt( b ) ) = lzcnt( a | b )
- min( tzcnt( a ), tzcnt( b ) ) = tzcnt( a | b )
- tzcnt( a ) + tzcnt( b ) = tzcnt( a * b )
Extracting up to k 1-bits from a word
The following codes keep the selected bits in the positions of the 1-bits in w, i.e., the result is a copy of w with only the least significant k 1-bits of w retained. All other bits are zero.
- pdep( (1<<k)-1, w )
- pdep( bzhi( ~0, k ), w )
One can also compact these bits in consecutive least-significant bit positions, resulting in a sequence of at most k consecutive 1-bits. For s = pdep( bzhi( ~0, k ), w ):
- pext( s, w ) = bzhi( ~0, popcnt( s ) ) = (1<<k)-1
Finding the bit position of the k-th set bit in a word
We assume k starts counting at zero, i.e., the 0-th 1-bit in 001010 is at position 1 (from lsb) and the 10th bit is at position 3.
- tzcnt( pdep( 1<<k, w ) )
