BSF

BSF finds the lowest set bit of its source and writes that bit’s index to the destination: for 0x28 it gives 3. ZF says whether there was a bit to find. For a nonzero source BSF clears ZF; for zero it sets ZF and does not write the destination at all, and the other flags are undefined. BSR is the scan from the other end.

Testing ZF#

Code that may see a zero source checks ZF right after the scan instead of testing the source first. __builtin_ffs(x), which returns the index plus 1, or 0 for no bit, shows how. GCC 14 at -O2 compiles it to

• bsf eax, edi,
• mov edx, -1 and cmove eax, edx, taking -1 when ZF is set,
• add eax, 1;

Clang 23 does the same with CMOVNE the other way round.

For __builtin_ctz, which C leaves undefined for 0, both compilers emit rep bsf instead, which runs as TZCNT where BMI1 exists and as BSF elsewhere; the TZCNT page explains where the two differ.

The unchanged destination#

Both vendors’ manuals now say that a zero source leaves the destination alone, so a register loaded beforehand acts as the result for zero: mov eax, 32 followed by bsf eax, edi gives 32 for x = 0. Intel’s manual adds that some older processors clear bits 63:32 of a 64-bit register when a 32-bit BSF finds no bit. Zen 5 and the Intel processor under KVM that recorded this page kept all 64 bits in every such case. Code meant for any x86-64 processor should still load the fallback value into the full register, or use TZCNT, which returns the operand size for zero.

Walking the set bits#

A loop that visits the set bits of a mask takes the lowest with BSF or TZCNT, handles it, and clears it with BLSR or with m & (m - 1), until the mask is 0; since the loop condition already excludes zero, the scan never meets an empty source. The instruction table of AMD’s Zen 5 guide lists BSF, like TZCNT, as one macro-op with a latency of one cycle.

In the optimization guide

What the optimization guide says about BSF, a line per claim. Each links to the claim in the guide, with its sources and where they differ.

Jaguar and Puma

• Integer execution: LZCNT and POPCNT take one cycle on either ALU and TZCNT two, while BSF and BSR are microcoded, of seven and eight macro-ops and 4 and 5 cycles, so the newer instructions are the better choice where the zero case allows.

Skylake to Cooper Lake

• Integer execution: Port 1 alone runs integer multiplication, PDEP and PEXT, popcnt, lzcnt, tzcnt, bsf, bsr and the double shifts, with a latency of three cycles and one a cycle in LLVM’s models, as on Golden Cove.

Zen and Zen+

• Integer execution: BSF and BSR are six macro-ops with a latency of three and four cycles, while LZCNT and POPCNT are one macro-op of one cycle and TZCNT two of two cycles. sources differ

Zen 2

• Integer execution: BSF and BSR are six macro-ops with a latency of three and four cycles, while LZCNT and POPCNT are one macro-op of one cycle and TZCNT two; LLVM’s model agrees.

Forms

Latency and throughput

Operation

What the forms do, in pseudocode that our tests run against results recorded on real processors. How to read.

s = src.read()
if s == 0:
    zf = 1
    # dest is not written, as both manuals say; Intel's adds
    # that some older processors clear bits 63:32 of it at a
    # 32-bit operand size
else:
    zf = 0
    for i in range(OSIZE):
        if s >> i & 1:
            dest.write(i)        # the number of the lowest 1 bit
            break
of = sf = af = pf = cf = UNDEFINED

Operands

Flags

Intrinsics

The C intrinsics of Clang 23.1.2 that compile to BSF, each with the form it compiles to and the Clang options it needs. The forms come from compiling every intrinsic and decoding the result with Intel XED; all intrinsics A–Z explains the method.

CPUID and processors

Each form belongs to an XED ISA set. A form can be used when the processor reports every CPUID bit of one of its ISA set's alternatives.

More General-purpose instructions

• AAA
• AAD
• AAM
• AAS
• ADC
• ADD
• AND
• BOUND
• BSR
• BSWAP
• BT
• BTC
• BTR
• BTS
• CALL
• CBW
• CDQ
• CDQE
• CLC
• CLD
• CLI
• CMC
• CMP
• CMPS
• CMPXCHG
• CMPXCHG8B
• CPUID
• CQO
• CWD
• CWDE
• DAA
• DAS
• DEC
• DIV
• ENTER
• IDIV
• IMUL
• IN
• INC
• INS

All 109 General-purpose instructions