不含循环的4的幂判断代码为何在汇编中生成带REP指令的循环？

问题背景 #

我编写了用于判断整数是否为4的幂的C++和C代码，代码中未包含显式循环，核心逻辑为检查整数仅设置一个比特位且该比特位处于奇数位置。原本预期生成无分支代码，但编译后的x86汇编中出现了两条跳转指令和一条rep指令。据我所知rep本质是汇编层面的循环，且该指令似乎由std::countr_zero/__builtin_ctz生成。我理解该循环受限于整数宽度（32位），时间复杂度仍为O(1)，但仍对出现循环感到惊讶。我的理解是否正确？这段代码在x86架构上属于循环吗？是否因为x86有popcount指令，但无计数前导/尾随零的指令导致？

附代码 #

C++版本

bool is_pow_4(unsigned a) {
    return (std::popcount(a) == 1) && (std::countr_zero(a) % 2 == 0);
}

C版本

int is_pow_4(unsigned a) {
   return (__builtin_popcount(a) == 1) && (__builtin_ctz(a) % 2 == 0);
}

汇编输出（C++） #

is_pow_4(unsigned int):
        lea     edx, [rdi-1]
        mov     ecx, edi
        xor     eax, eax
        xor     ecx, edx
        cmp     edx, ecx
        jb      .L7
.L1:
        ret
.L7:
        mov     eax, 1
        test    edi, edi
        je      .L1
        xor     eax, eax
        rep bsf eax, edi
        not     eax
        and     eax, 1
        ret

C版本汇编输出类似。

解答 #

1. rep bsf是否属于循环 #

你的理解完全正确：rep bsf确实是汇编层面的循环结构，但它的循环次数被严格限制在整数的位宽范围内（比如32位整数最多循环32次），因此时间复杂度依然是O(1)，不会随输入数值的大小变化。不过现代x86 CPU对这类指令做了硬件优化，实际执行时并不会逐位循环，而是通过专用硬件电路直接计算结果，效率和普通单周期指令相当。

2. 跳转与rep指令的成因 #

• 跳转指令：来自代码中&&的短路求值特性——当std::popcount(a) == 1不成立时，编译器会直接返回false，无需执行后续的countr_zero判断。生成跳转是编译器的合理性能优化，避免不必要的计算。
• rep bsf的由来：早期x86架构没有专门的计数尾随零指令（如BMI1指令集中的TZCNT），编译器只能用rep bsf模拟__builtin_ctz/std::countr_zero的功能。bsf本身是“位扫描向前”指令，配合rep前缀后会从最低位开始扫描第一个置1的位，最终得到的就是尾随零的数量。如果你的CPU支持BMI1指令集，只需添加-mbmi1编译选项，编译器就会生成无循环的TZCNT指令，替代rep bsf。

3. popcount的无循环实现 #

x86从SSE4.2指令集开始就提供了POPCNT专用指令，因此编译器会直接生成该指令实现std::popcount/__builtin_popcount，这部分确实是无循环的。

内容的提问来源于stack exchange，提问作者bolov