Skip to content
Reverse Engineering

Instructions

x86-64

BSF / BSR / POPCNT / LZCNT / TZCNT

Bit-counting instructions: find the first or last set bit, count leading or trailing zeros, or count how many bits are set. The hardware behind ffs, clz and popcount.

These instructions answer questions about which bits are set in a word. They map directly to common C intrinsics and standard-library helpers.

Bit scan — BSF / BSR

BSF dst, src (bit scan forward) returns the index of the lowest set bit; BSR (reverse) returns the index of the highest set bit.

asm
bsf eax, ecx      ; eax = index of lowest set bit of ecx
bsr eax, ecx      ; eax = index of highest set bit (= floor(log2))

Gotcha: if the source is 0, the result register is undefined and ZF is set to 1. Correct code checks ZF (or guards the zero case) first — a missing zero check is a real bug to look for.

Count zeros — LZCNT / TZCNT

LZCNT counts leading zeros, TZCNT counts trailing zeros. They are the well-defined modern replacements for BSR/BSF:

  • For a non-zero input, TZCNT equals BSF, and LZCNT equals (width-1) - BSR.
  • For a zero input they return the operand width (32 or 64) instead of being undefined, and set CF. Much safer.
  • Encoding quirk: LZCNT/TZCNT are BSR/BSF with an F3 (REP) prefix. On a CPU without BMI/ABM support the prefix is ignored and the instruction runs as BSR/BSF — silently different behaviour on the zero case. Worth knowing when reversing code that must run on old hardware.

Population count — POPCNT

POPCNT dst, src counts the number of set bits (the Hamming weight).

asm
popcnt eax, ecx   ; eax = number of 1-bits in ecx

Reverse-engineering notes

  • These decompile to recognisable intrinsics: BSF/TZCNT → __builtin_ctz / _tzcnt; BSR/LZCNT → __builtin_clz / _lzcnt; POPCNT → __builtin_popcount / _mm_popcnt.
  • BSR is the standard way to compute an integer log2 / find the highest power of two — common in allocators (size-class buckets), hash-table sizing, and bignum normalisation.
  • TZCNT/BSF over a bitmap, often inside a loop that then clears the lowest bit with x & (x-1) (blsr), is the canonical "iterate over set bits" pattern — used everywhere from scheduler run-queues to chess engines.
  • A lone POPCNT in otherwise integer-heavy code can hint at checksums, error-correcting codes, or similarity/Hamming-distance computations.

See also: BT / BTS / BTR / BTC · AND / OR / NOT · Shift & rotate.