Bitscanning

Bitscanning refers to a family of techniques used to locate and count set bits within a binary word. The primary goals are to find the position of the least significant set bit, the most significant set bit, or to determine how many bits are set in a word. These operations are fundamental in low-level programming, data structures, and performance-critical code.

Common operations include counting trailing zeros (CTZ), counting leading zeros (CLZ), and the bit scan family such as bit scan forward (BSF) and bit scan reverse (BSR). CTZ yields the number of zero bits following the least significant 1, effectively giving the index of the LSB when the word is nonzero. CLZ provides the number of leading zeros, giving the position of the MSB in nonzero words. BSF and BSR return the index of the least or most significant set bit, respectively. Population count (popcount) counts the total number of set bits. Behaviors for zero inputs vary by instruction set and language; many instructions are undefined for zero, so zero checks are common before invocation.

Implementation and portability vary. Modern compilers expose built-in intrinsics such as __builtin_ctz, __builtin_clz, __builtin_ctzll, __builtin_clzll in C/C++, and similar primitives in other languages. Some architectures provide dedicated instructions (for example, x86 BSF/BSR/POPCNT, ARM CLZ/CTZ). In software-only contexts, bit scanning can be implemented via de Bruijn sequences, lookup tables, or binary search on bit patterns.

Bitscanning is widely used in areas such as bitboard representations in games, sparse data processing, memory allocators, network mask manipulation, and algorithms that require quick position or cardinality information about bitsets.