这个不包含任何循环的简单代码是否会使用 REP 指令在汇编中生成循环？ [重复]

Question

我正在使用这段代码来检查一个整数是否是 4 的幂：

// C++ version

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

// C version

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

基本上，我检查是否只有一位被设置，并且它位于一个奇怪的位置。

我期待一个无分支代码，但是我看到两个跳转和一个

rep

指令。据我所知，

rep

基本上是一个循环，但在汇编级别。看起来

std::countr_zero

/

__builtin_ctz

生成了

rep

指令。

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 输出 类似。

我知道循环是受整数（32）的宽度限制的，所以我认为代码的复杂度是

O(1)

，但我仍然很惊讶地发现了一个循环。

我的理解正确吗？这段代码是 x86 上的循环吗？这是因为虽然有 x86 popcount 指令，但没有计数前导/尾随零 x86 指令？

Answer 1

代码运行时间为 O(1)，并且rep bsf 不是循环，它是在固定时间内运行的单个指令。编译器选择此实现是因为 x86 上没有 std::countr_zero 对应项，因此使用 bsf 来获取第一个位集