如何让 BSR 指令在 64 位上工作？
How to get BSR instruction to work on 64 bits?
我正在尝试查找无符号 64 位整数的前导位。我正在使用 BSR，因为我的处理器没有 LZCNT 指令。我的问题是，一旦输入正好是 2^32，它 returns 2^64 作为前导位值，然后循环返回直到 2^64。
这是我的代码：
unsigned long int LeadingBit(unsigned long int a) {
if(a==0)
return 0;
unsigned long int nlb;
asm (
"BSR %1, %0 \n"
: "=r" (nlb)
: "mr" (a)
: "cc"
);
return 1<<nlb;
}
这段代码的目的是能够输入一个 64 位整数，并将其 return 前导 1 位置的值。例如：
一 = 65 (1000001)
returns 1000000.
正如Michael Petch所指出的，这一行就是问题所在：
return 1<<nlb;
计算发生在 int，而不是 unsigned long。将其替换为：
return 1UL<<nlb;
虽然 Michael/Florian 的修复可能是最简单的，但也许不是最好的。
您现有的代码（使用 1UL 修改）编译为：
xor eax, eax
test rdi, rdi
je .L1
mov eax, 1
BSR rdi, rcx
sal rax, cl
.L1:
ret
不错，但不是测试零，然后调用 BSR（它也检查零），怎么样：
unsigned long int LeadingBit(unsigned long int a) {
unsigned long int nlb;
bool z;
asm (
"BSR %[a], %[nlb]"
: [nlb] "=r" (nlb), "=@ccz"(z)
: [a] "mr" (a)
);
unsigned long int one;
if (!z)
one = 1;
else
one = 0;
return one << nlb;
}
由于 BSR 将 ZF 设置为零，此代码使用它将 one 设置为 0 或 1，具体取决于。这个 asm 非常干净 (gcc 9.2 -O2):
BSR rdi, rcx
setne al
movzx eax, al
sal rax, cl
ret
Flag Output Operands 下的文档中描述了“=@ccz”约束。基本上就是说 "The value of this variable is taken from the Z (C)ondition (C)ode."
编辑：看到 Peter 提出意见我并不感到惊讶，但令我惊讶的是他没有 post 他自己的替代方案。
这是我将他的评论翻译成代码的尝试。这可能比 OP 感兴趣的更复杂，但为了完整起见：
unsigned long int LeadingBit(unsigned long int a) {
unsigned long int bit;
unsigned long int res;
asm (
"BSR %[a], %[bit] \n\t" // sets both (bit) and ZF
"BTS %[bit], %[res] \n\t" // sets the corresponding bit in (res) and
// carry flag, but *doesn't* change ZF
"CMOVZ %[zero], %[res]" // reset res to 0 if BSR detected a==0
: [bit] "=&r" (bit), [res] "=&r"(res)
: [a] "mr" (a), [zero] "r"(0UL), "[res]"(0UL)
: "cc"
);
return res;
}
虽然 BSR/BTS/CMOVZ 非常直截了当，但您的代码维护人员可能会为这些带有约束的废话而烦恼。
所以，解释一下发生了什么。
"=&r"(res) 将保留 return 值。 & 用于表示它不能与任何其他参数共享一个寄存器。需要明确的是，仅仅因为您将约束声明为“=r”，并不意味着您将获得一个 unique 寄存器，除非您使用 &。通过减少使用的寄存器数量，这可能是一件好事，但在这种情况下并不是那么多。如果编译器决定对 %[zero] 和 %[res] 使用相同的寄存器，那将导致 CMOVZ 失败。"[res]"(0UL) 表示在进入 asm 时，无论用于 %[res] 的寄存器都应初始化为零。是的，我们可以在 asm 中执行此操作，但是通过将其放入 C 代码中，它允许编译器以相对于周围代码最有效的任何方式执行此操作。哎呀，它周围可能已经有一个归零寄存器，它只是用于其他用途。BTS 允许您直接在寄存器中设置位号。它通常比使用 SAL 更快（这就是 Peter 所说的 SAL 的“3 微指令”与 BTS 的 1 微指令），但与 BSR 一样，gcc 没有它的内在特性。虽然它 return 进位标志中指定位的现有值（这就是 BTS 的 T 部分的意思），但它 不会 修改零标志。这让我们仍然可以在 BTS 之后进行 CMOVZ。以这种方式更新 "part" 标志寄存器在某些处理器上可能效率低下，但对于较新的处理器来说效率不高。
这是输出：
xorl %edx, %edx
movq %rdx, %rax
BSR %rdi, %rcx
BTS %rcx, %rax
CMOVZ %rdx, %rax
ret
我有点怀疑 movq（为什么不是 xor 或 movl？），但我确信这是有充分理由的。我假设与 'aliasing' 有关。
如果 perf 具有足够高的优先级（尽管 OP 从未说过），我还可以考虑做一件事。如果 LeadBit 可能会用常量调用，编译器通常可以在编译时预先计算很多围绕它的数学，而不是当你 运行 程序时。
但是，gcc 不能 通过内联汇编进行预计算。如果可以使用常量调用 LeadBit，您可以将我在此处显示的代码用 if (__builtin_constant_p(a)) 包装起来，以查看 a 是否为常量，然后使用 __builtin_clzll 等计算它 "slow" 方式。我说 "slow," 但在编译时计算值（即使是缓慢的方式）将导致更快的可执行文件。由于（根据定义）__builtin_constant_p 的值在编译时已知，因此对于 LeadingBit 的任何调用只会生成 if 的一个分支。
TL:DR：如果你要优化整个事情并打败编译器，你应该只使用内联汇编。否则使用像 __builtin_clzll 或 GCC-only __builtin_ia32_bsrdi
这样的内在函数
您的实际问题与内联汇编无关。
1 的类型为 int，与大多数运算符不同，<< 不会提升左侧以匹配右侧。因此，您将 int 移动了超过 31 位，这是未定义的行为。实际上，您会得到一个 32 位操作数大小的偏移，您可以通过查看编译器的 asm 输出注意到这一点。 （无论何时使用内联汇编，通常都是一个好主意。）
您不需要内联汇编；使用 GNU C 内置函数很容易表达。
但是，如果性能至关重要，您可能希望使用内联汇编来解决编译器对当前微体系结构在移位部分的优化失误，特别是如果您在没有 BMI2 的情况下进行编译以在 Intel 上实现高效的变量计数移位 CPUs.
请注意 bsr 在 AMD CPUs 上相当慢，而 lzcnt 在所有支持它的 CPUs 上都很快.在 Intel 上，两者都很快。但与 bsf/tzcnt 不同的是，这些指令即使对于非零输入也会产生不同的结果，因此使用 rep bsr 在较新的 CPU 上获得快速 lzcnt 是没有用的tzcnt 有时也是如此。 （tzcnt 运行s 在旧 CPUs 上作为 bsf，lzcnt 运行s 在旧 CPUs 上作为 bsr。这是因为 lzcnt 的编码是前面的 REP 前缀bsr)
不幸的是 bsr 在 Atom/Silvermont 上也很慢。与 Goldmont Plus 类似：11 微指令、9 周期延迟和 8 周期吞吐量。
查看我在 Find most significant bit (left-most) that is set in a bit array 上的回答，了解 运行各种 编译器对 63-__builtin_clzll(x); 的愚蠢程度，这可以优化回 bsr，但没有。
GCC（不是 clang）有一个内在的 __builtin_ia32_bsrdi 用于 64 位 bsr，并且两者都支持 _bit_scan_reverse 用于 32 位。
最明显的写法是适用于 GCC 支持的任何目标的可移植代码:
uint64_t LeadingBitIsolate_gnuc(uint64_t a)
{
static_assert( CHAR_BIT * sizeof(unsigned long) == 64, "__builtin_clzll isn't 64-bit operand size");
uint64_t bit = 63-__builtin_clzll(a); // BSR
return a ? (1ULL << bit) : 0; // ULL is guaranteed to be at least a 64-bit type
}
如果 a 曾经是编译时常量，则通过此函数的常量传播有效。 使用内联 asm 总是会失败，除非你使用类似 if(__builtin_constant_p(a)) { non-asm version } else { asm version}。 (https://gcc.gnu.org/wiki/DontUseInlineAsm)
我使用 uint64_t 来移植到 x86-64 目标，其中 unsigned long 是 32 位类型。 （Linux x32（ILP32 ABI）和 MS Windows x64）。也适用于非 x86 目标，因为它不使用任何内联 asm。
编译成非常糟糕的 asm
# gcc9.2 -O3 -mtune=skylake
LeadingBitIsolate_gnuc(unsigned long):
movq %rdi, %rax
testq %rdi, %rdi
je .L4
bsrq %rdi, %rax
movl , %ecx
xorq , %rax # bit = 63 - bit in the low 6 bits, 2's complement bithack
subl %eax, %ecx # bit = 63 - bit
movl , %eax # 1 uop
salq %cl, %rax # 3 uops
.L4:
ret
使用 BSR64 = __builtin_ia32_bsrdi 从我对 Find most significant bit (left-most) that is set in a bit array 的回答中我们从 GCC 得到这个（和类似的使用 cmov来自 clang 和 ICC）。 ICC/MSVC 为 BSR 的 ZF 输出提供 return 一个 bool 的内在函数。 test/je 与现代 x86 上的 je 具有相同的成本，但在 cmov 前面保存 test 指令确实有价值。
// See the linked answer for the ICC/MSVC part of this
#ifdef __GNUC__
#ifdef __clang__
static inline unsigned BSR64(uint64_t x) {
return 63-__builtin_clzll(x);
// gcc/ICC can't optimize this back to just BSR, but clang can and doesn't provide alternate intrinsics
// update: clang8.0 regressed here but still doesn't do __builtin_ia32_bsrdi
}
#else
#define BSR64 __builtin_ia32_bsrdi
#endif
#include <x86intrin.h>
#define BSR32(x) _bit_scan_reverse(x)
#endif
uint64_t LeadingBitIsolate_gnuc_v2(uint64_t a)
{
uint64_t bit = BSR64(a);
return a ? (1ULL << bit) : 0;
}
这与 GCC 编译得更好，至少对于 BSR 部分。但仍然不是换班部分。
# gcc -O3 -mtune=skylake
LeadingBitIsolate_gnuc_v2(unsigned long):
movq %rdi, %rax
testq %rdi, %rdi
je .L9
bsrq %rdi, %rcx
movl , %eax
salq %cl, %rax # missed optimization: xor-zero + bts would be much better especially with tune=skylake
.L9:
ret
从好的方面来说，我们通过使用 BSR 内在优化了 大部分 的 BSR 开销。 它仍然可以在 CPUs 上编译为 LZCNT，这是更好的选择，例如随着 clang -march=znver1 (Ryzen)。 GCC 仍然使用 BSR，但 clang 使用 63-lzcnt，这将 运行 在 AMD 上更快。
63-__builtin_clzll 可移植到非 x86，但 __builtin_ia32_bsrdi 不是。 （DI = 双字整数 = 64 位）。
但是编译器仍然知道发生了什么，并且可以将其优化到周围的代码中， 和编译时常量输入。
例如如果输入=0，它也可以分支到其他东西上，只测试一次。它知道输入只有一个位集，所以理论上，如果您将它用作除数，编译器可能足够聪明，可以与 res-1 进行 AND 而不是使用缓慢的 div 指令. （除以零是 UB，因此编译器可以假设这没有发生，甚至可能在内联后优化掉其中的 a==0 ? 部分。）
使用可用于 SHLX 的 BMI2 对其进行编译将使它在现代 Intel 上高效。
使用内联 asm 解决 Sandybridge-family 错过的优化
SnB-family 的变量计数移位比平常慢: 检查计数是否为零并有条件地将移位的标志结果合并到旗帜。 （如果 cl=0，shl %cl, %reg 必须保留 FLAGS 不变。这是 "x86 tax" 的一部分，高性能 x86 CPUs 必须支付超标量乱序执行。）
AMD 显然将轮班管理为一个 uop，没有限制/惩罚。
因此 bts 到清零寄存器是实现 1ULL << count 的更好选择，尤其是在英特尔 CPUs 上，异或清零非常便宜，并且 bts reg,reg是单个 uop（而不是 Ryzen 上的 2 个）。
与@DavidWohlferd 的回答中的版本（基于我的评论）相比，这通过在 a==0 的情况下使用 a 作为零来保存指令，而不需要额外的归零寄存器.评论讨论性能影响。
#include <stdint.h>
#include <limits.h>
uint64_t LeadingBitIsolate_asm(uint64_t a)
{
uint64_t bit;
uint64_t bts_target = 0;
asm (
"BSR %[a], %[bit] \n\t" // ZF = (a==0)
"BTS %[bit], %[res] \n\t" // sets CF = old bit = 0 but not ZF
// possible partial-flag stall on some CPUs for reading ZF after writing CF
// but not SnB-family
"CMOVZ %[a], %[res]" // res = a (= 0) if BSR detected a==0
: [bit] "=r" (bit), [res] "+r"(bts_target) // no early clobber: input read before either output written
: [a] "r" (a)
: "cc" // redundant but not harmful on x86: flags clobber is always implied
);
return bts_target;
}
在 BTS 写入 CF 后读取 ZF 对于较旧的英特尔 CPUs 是危险的，它将导致 a partial-flag stall. See also
GCC 9.2 为我们提供了一个在 Skylake 上只有 4 微指令的序列。 (https://agner.org/optimize/)。异或归零需要前端微指令，但在 Sandybridge 系列上不需要后端执行单元（0 未融合域微指令）。
在 Haswell 和更早版本上是 5 微指令，其中 cmov 是 2 微指令/2c 延迟。既然你说你的 CPU 不支持 lzcnt，你可能有一个 IvyBridge 或更早的 (2 uop cmov)，或者一个旧的 AMD。
如果 input=0 预计很少发生或永远不会发生，那么分支可能是值得的， 特别是如果这是延迟的关键路径的一部分。特别是在较旧的 Intel 上，cmov 是 2 微指令。
gcc9.2 -O3 -mtune=skylake
LeadingBitIsolate_asm(unsigned long):
xorl %eax, %eax
BSR %rdi, %rdi
BTS %rdi, %rax
CMOVZ %rdi, %rax
ret
"rm"(a) 输入约束是可能的，但是
- 我们读了两遍所以最好让编译器载入寄存器一次
- clang 是愚蠢的，当它是一个选项时总是选择
m，即使这意味着溢出一个已经在寄存器中的值。 clang (LLVM) inline assembly - multiple constraints with useless spills / reloads
bsr 对现有 CPU 具有 "false" 依赖性，因此如果编译器碰巧为 res 和 [=37= 选择相同的寄存器会更好] 而不是写一个新的寄存器。如果以后不需要 a，通常会发生这种情况。
BSR 并不是真正的错误依赖：如果输入为零，则目标保持不变。 AMD 甚至记录了这一点，但英特尔在离开 their documentation saying "undefined" contents.
的同时在他们的硬件中实现了它
无论如何我们都无法利用这一点，我们有 65 种可能的输出，而 BTS 进入归零 reg 只能产生 64 种不同的输出。
您可能会想在保存 1 的寄存器上使用 rcl（循环进位），但首先 rcl %cl, %reg 非常慢，其次它仍然屏蔽& 63 的移位，因此它无法将 1 一直移位到 CF。
没有部分标志停顿，较旧的 Intel 上的关键路径更短
使用 BTC 并利用 BSR 零输入行为，我们可以制作一个版本，该版本可能在旧的 Intel P6 系列上更好，例如 Nehalem 和 Core 2（其中 cmov 是 2 微码，部分标志停顿是一个问题）。
虽然它不保存微指令，因为它需要一个额外的异或归零寄存器。它确实缩短了关键路径延迟，如果我们使用 test/setz 与 3-cycle-latency bsr 并行使用，而不是使用 BSR 的 ZF 输出，它可能会进一步缩短.或者，如果编译器已经对输入进行了数学计算，它可能已经适当地设置了 ZF。很遗憾，无法查询。
btc=补=翻转一点，而不是无条件设置。如果目标寄存器是 1 而不是 0，如果我们知道这种情况的位索引，那么这会产生零结果。
xor-zero / set flags / setcc 是标准惯用语，通常至少与 set flags / setcc / movzx 一样高效，因为 xor-zeroing 甚至比 movzx 更便宜，而且它不在延迟的关键路径上。 setcc 是所有 x86-64 CPUs 上的 1-uop 指令。
// depends on BSR behaviour that only AMD documents, but all real CPUs implement (for now?)
// it seems unlikely that this will change, though.
// The main advantage of this version is on P6-family and early Sandybridge
// where it definitely does work safely.
uint64_t LeadingBitIsolate_asm_p6(uint64_t a)
{
uint64_t btc_target;
uint64_t bit = 0;
//bool input_was_zero;
asm (
"xor %k[res], %k[res]\n\t" // make sure we avoid P6-family partial-reg stalls with setz + reading full reg by forcing xor-zeroing, not MOV
"bsr %[a], %[bit] \n\t" // bit=count or unmodified (if a==0)
"setz %b[res]\n\t" // res = (a==0)
"btc %[bit], %[res] \n\t" // flip a bit. For a==0, flips bit 0 which SETZ set to 1
: [bit] "+r" (bit), [res] "=&q"(btc_target) // q = reg accessible as low-8, like RAX has AL. Any x86-64 reg
// early-clobber: [res] is written before a, but [bit] isn't.
// ,"=@ccz" (input_was_zero) // optional GCC6 flag output. Or "=@ccc" to read from CF (btc result) and avoid partial-flag stalls
: [a] "r" (a)
: "cc"
);
return btc_target;
//return input_was_zero;
}
GCC9 和 t运行k 有一个奇怪的寄存器分配错过优化，它在 r8 中产生 res 并且必须 mov 它返回到 RAX。
gcc8.3 -O3 -mtune=nehalem
LeadingBitIsolate_asm_p6(unsigned long):
xorl %edx, %edx # compiler-generated
xor %eax, %eax # inline asm
bsr %rdi, %rdx
setz %al
btc %rdx, %rax
ret
在英特尔 CPU 上，如 Core2、Nehalem 和 Sandybridge 系列，这是 5 微指令，没有停顿。 BSR 有 3 个周期的延迟，其余的有 1 个周期的延迟。从 RDI 输入到 RAX 输出，延迟为 3 + 1 + 1 = 5 个周期。 （setz 必须等待 BSR 的输出。正如我上面提到的，在 bsr 之前 a 上的 test/setz 将允许指令级并行性，在 test 将关键路径延迟缩短另一个周期。）
在 AMD Bulldozer 系列 / Ryzen 上，因为 bsr 而贵得多。 setz 仍然是 1 微指令，btc 是 2 微指令。
在Atom/Silvermont，因为BSR也很贵
除非您使用 lzcnt 制作版本并执行 运行 时间调度或其他操作，否则没有解决慢速 BSR 的方法。 （可能对于 调用 这个函数的循环；调用开销可能仍然比在具有 8 到 10 uop bsr 的 CPU 上使用 bsr 更糟糕. 特别是 Ryzen 具有高 uop 吞吐量。)
这对于 a!=0 的情况非常有效，将 BTC 放入归零寄存器以翻转 BSR 找到的位索引处的位。
对于a==0情况：
# starting: rdx=rax=0
bsr %rdi, %rdx # leaves RDX=0 (unmodified) and sets ZF
setz %al # sets RAX=1
btc %rdx, %rax # flips bit 0 of RAX, changing it back to 0
# rax = 0 (result), rdx = 0 (bitpos)
当我在 C 中使用两个 "+r" 输入都设置为零时，GCC 决定异或零 EAX/RAX，但使用 mov %rax, %rdx 将其复制到 RDX！ （浪费 REX 前缀）。这在 Sandybridge 上显然更糟，它消除了异或归零但没有消除移动。不过，它在 AMD Ryzen 上更好，它具有 mov-elimination，但仍然需要一个用于异或归零的后端 uop。
用 mov 复制 0 与异或归零在 P6 系列（Core2 / Nehalem）上基本上是中性的，除了只有异或归零避免写入 AL 的部分寄存器停顿使用 setcc 并使用 btc 读取 RAX。所以我将异或归零放在内联 asm 中，以确保它实际上是异或归零，而不是 gcc 为 res 选择的 mov。 ().
请注意，对于输入=0 的情况，BSR 保留目标未修改的行为 仅由 AMD 记录，未由 Intel 正式记录。但它 是 由所有英特尔的硬件实现的，至少是任何支持 64 位模式的硬件。关于 Via Nano 或古老的 Intel 的 IDK。
我正在尝试查找无符号 64 位整数的前导位。我正在使用 BSR，因为我的处理器没有 LZCNT 指令。我的问题是，一旦输入正好是 2^32，它 returns 2^64 作为前导位值，然后循环返回直到 2^64。
这是我的代码：
unsigned long int LeadingBit(unsigned long int a) {
if(a==0)
return 0;
unsigned long int nlb;
asm (
"BSR %1, %0 \n"
: "=r" (nlb)
: "mr" (a)
: "cc"
);
return 1<<nlb;
}
这段代码的目的是能够输入一个 64 位整数，并将其 return 前导 1 位置的值。例如： 一 = 65 (1000001) returns 1000000.
正如Michael Petch所指出的，这一行就是问题所在：
return 1<<nlb;
计算发生在 int，而不是 unsigned long。将其替换为：
return 1UL<<nlb;
虽然 Michael/Florian 的修复可能是最简单的，但也许不是最好的。
您现有的代码（使用 1UL 修改）编译为：
xor eax, eax
test rdi, rdi
je .L1
mov eax, 1
BSR rdi, rcx
sal rax, cl
.L1:
ret
不错，但不是测试零，然后调用 BSR（它也检查零），怎么样：
unsigned long int LeadingBit(unsigned long int a) {
unsigned long int nlb;
bool z;
asm (
"BSR %[a], %[nlb]"
: [nlb] "=r" (nlb), "=@ccz"(z)
: [a] "mr" (a)
);
unsigned long int one;
if (!z)
one = 1;
else
one = 0;
return one << nlb;
}
由于 BSR 将 ZF 设置为零，此代码使用它将 one 设置为 0 或 1，具体取决于。这个 asm 非常干净 (gcc 9.2 -O2):
BSR rdi, rcx
setne al
movzx eax, al
sal rax, cl
ret
Flag Output Operands 下的文档中描述了“=@ccz”约束。基本上就是说 "The value of this variable is taken from the Z (C)ondition (C)ode."
编辑：看到 Peter 提出意见我并不感到惊讶，但令我惊讶的是他没有 post 他自己的替代方案。
这是我将他的评论翻译成代码的尝试。这可能比 OP 感兴趣的更复杂，但为了完整起见：
unsigned long int LeadingBit(unsigned long int a) {
unsigned long int bit;
unsigned long int res;
asm (
"BSR %[a], %[bit] \n\t" // sets both (bit) and ZF
"BTS %[bit], %[res] \n\t" // sets the corresponding bit in (res) and
// carry flag, but *doesn't* change ZF
"CMOVZ %[zero], %[res]" // reset res to 0 if BSR detected a==0
: [bit] "=&r" (bit), [res] "=&r"(res)
: [a] "mr" (a), [zero] "r"(0UL), "[res]"(0UL)
: "cc"
);
return res;
}
虽然 BSR/BTS/CMOVZ 非常直截了当，但您的代码维护人员可能会为这些带有约束的废话而烦恼。
所以，解释一下发生了什么。
"=&r"(res)将保留 return 值。&用于表示它不能与任何其他参数共享一个寄存器。需要明确的是，仅仅因为您将约束声明为“=r”，并不意味着您将获得一个 unique 寄存器，除非您使用&。通过减少使用的寄存器数量，这可能是一件好事，但在这种情况下并不是那么多。如果编译器决定对 %[zero] 和 %[res] 使用相同的寄存器，那将导致 CMOVZ 失败。"[res]"(0UL)表示在进入 asm 时，无论用于 %[res] 的寄存器都应初始化为零。是的，我们可以在 asm 中执行此操作，但是通过将其放入 C 代码中，它允许编译器以相对于周围代码最有效的任何方式执行此操作。哎呀，它周围可能已经有一个归零寄存器，它只是用于其他用途。BTS允许您直接在寄存器中设置位号。它通常比使用SAL更快（这就是 Peter 所说的 SAL 的“3 微指令”与 BTS 的 1 微指令），但与 BSR 一样，gcc 没有它的内在特性。虽然它 return 进位标志中指定位的现有值（这就是 BTS 的 T 部分的意思），但它 不会 修改零标志。这让我们仍然可以在 BTS 之后进行 CMOVZ。以这种方式更新 "part" 标志寄存器在某些处理器上可能效率低下，但对于较新的处理器来说效率不高。
这是输出：
xorl %edx, %edx
movq %rdx, %rax
BSR %rdi, %rcx
BTS %rcx, %rax
CMOVZ %rdx, %rax
ret
我有点怀疑 movq（为什么不是 xor 或 movl？），但我确信这是有充分理由的。我假设与 'aliasing' 有关。
如果 perf 具有足够高的优先级（尽管 OP 从未说过），我还可以考虑做一件事。如果 LeadBit 可能会用常量调用，编译器通常可以在编译时预先计算很多围绕它的数学，而不是当你 运行 程序时。
但是，gcc 不能 通过内联汇编进行预计算。如果可以使用常量调用 LeadBit，您可以将我在此处显示的代码用 if (__builtin_constant_p(a)) 包装起来，以查看 a 是否为常量，然后使用 __builtin_clzll 等计算它 "slow" 方式。我说 "slow," 但在编译时计算值（即使是缓慢的方式）将导致更快的可执行文件。由于（根据定义）__builtin_constant_p 的值在编译时已知，因此对于 LeadingBit 的任何调用只会生成 if 的一个分支。
TL:DR：如果你要优化整个事情并打败编译器，你应该只使用内联汇编。否则使用像 __builtin_clzll 或 GCC-only __builtin_ia32_bsrdi
您的实际问题与内联汇编无关。
1 的类型为 int，与大多数运算符不同，<< 不会提升左侧以匹配右侧。因此，您将 int 移动了超过 31 位，这是未定义的行为。实际上，您会得到一个 32 位操作数大小的偏移，您可以通过查看编译器的 asm 输出注意到这一点。 （无论何时使用内联汇编，通常都是一个好主意。）
您不需要内联汇编；使用 GNU C 内置函数很容易表达。
但是，如果性能至关重要，您可能希望使用内联汇编来解决编译器对当前微体系结构在移位部分的优化失误，特别是如果您在没有 BMI2 的情况下进行编译以在 Intel 上实现高效的变量计数移位 CPUs.
请注意 bsr 在 AMD CPUs 上相当慢，而 lzcnt 在所有支持它的 CPUs 上都很快.在 Intel 上，两者都很快。但与 bsf/tzcnt 不同的是，这些指令即使对于非零输入也会产生不同的结果，因此使用 rep bsr 在较新的 CPU 上获得快速 lzcnt 是没有用的tzcnt 有时也是如此。 （tzcnt 运行s 在旧 CPUs 上作为 bsf，lzcnt 运行s 在旧 CPUs 上作为 bsr。这是因为 lzcnt 的编码是前面的 REP 前缀bsr)
不幸的是 bsr 在 Atom/Silvermont 上也很慢。与 Goldmont Plus 类似：11 微指令、9 周期延迟和 8 周期吞吐量。
查看我在 Find most significant bit (left-most) that is set in a bit array 上的回答，了解 运行各种 编译器对 63-__builtin_clzll(x); 的愚蠢程度，这可以优化回 bsr，但没有。
GCC（不是 clang）有一个内在的 __builtin_ia32_bsrdi 用于 64 位 bsr，并且两者都支持 _bit_scan_reverse 用于 32 位。
最明显的写法是适用于 GCC 支持的任何目标的可移植代码:
uint64_t LeadingBitIsolate_gnuc(uint64_t a)
{
static_assert( CHAR_BIT * sizeof(unsigned long) == 64, "__builtin_clzll isn't 64-bit operand size");
uint64_t bit = 63-__builtin_clzll(a); // BSR
return a ? (1ULL << bit) : 0; // ULL is guaranteed to be at least a 64-bit type
}
如果 a 曾经是编译时常量，则通过此函数的常量传播有效。 使用内联 asm 总是会失败，除非你使用类似 if(__builtin_constant_p(a)) { non-asm version } else { asm version}。 (https://gcc.gnu.org/wiki/DontUseInlineAsm)
我使用 uint64_t 来移植到 x86-64 目标，其中 unsigned long 是 32 位类型。 （Linux x32（ILP32 ABI）和 MS Windows x64）。也适用于非 x86 目标，因为它不使用任何内联 asm。
# gcc9.2 -O3 -mtune=skylake
LeadingBitIsolate_gnuc(unsigned long):
movq %rdi, %rax
testq %rdi, %rdi
je .L4
bsrq %rdi, %rax
movl , %ecx
xorq , %rax # bit = 63 - bit in the low 6 bits, 2's complement bithack
subl %eax, %ecx # bit = 63 - bit
movl , %eax # 1 uop
salq %cl, %rax # 3 uops
.L4:
ret
使用 BSR64 = __builtin_ia32_bsrdi 从我对 Find most significant bit (left-most) that is set in a bit array 的回答中我们从 GCC 得到这个（和类似的使用 cmov来自 clang 和 ICC）。 ICC/MSVC 为 BSR 的 ZF 输出提供 return 一个 bool 的内在函数。 test/je 与现代 x86 上的 je 具有相同的成本，但在 cmov 前面保存 test 指令确实有价值。
// See the linked answer for the ICC/MSVC part of this
#ifdef __GNUC__
#ifdef __clang__
static inline unsigned BSR64(uint64_t x) {
return 63-__builtin_clzll(x);
// gcc/ICC can't optimize this back to just BSR, but clang can and doesn't provide alternate intrinsics
// update: clang8.0 regressed here but still doesn't do __builtin_ia32_bsrdi
}
#else
#define BSR64 __builtin_ia32_bsrdi
#endif
#include <x86intrin.h>
#define BSR32(x) _bit_scan_reverse(x)
#endif
uint64_t LeadingBitIsolate_gnuc_v2(uint64_t a)
{
uint64_t bit = BSR64(a);
return a ? (1ULL << bit) : 0;
}
这与 GCC 编译得更好，至少对于 BSR 部分。但仍然不是换班部分。
# gcc -O3 -mtune=skylake
LeadingBitIsolate_gnuc_v2(unsigned long):
movq %rdi, %rax
testq %rdi, %rdi
je .L9
bsrq %rdi, %rcx
movl , %eax
salq %cl, %rax # missed optimization: xor-zero + bts would be much better especially with tune=skylake
.L9:
ret
从好的方面来说，我们通过使用 BSR 内在优化了 大部分 的 BSR 开销。 它仍然可以在 CPUs 上编译为 LZCNT，这是更好的选择，例如随着 clang -march=znver1 (Ryzen)。 GCC 仍然使用 BSR，但 clang 使用 63-lzcnt，这将 运行 在 AMD 上更快。
63-__builtin_clzll 可移植到非 x86，但 __builtin_ia32_bsrdi 不是。 （DI = 双字整数 = 64 位）。
但是编译器仍然知道发生了什么，并且可以将其优化到周围的代码中， 和编译时常量输入。
例如如果输入=0，它也可以分支到其他东西上，只测试一次。它知道输入只有一个位集，所以理论上，如果您将它用作除数，编译器可能足够聪明，可以与 res-1 进行 AND 而不是使用缓慢的 div 指令. （除以零是 UB，因此编译器可以假设这没有发生，甚至可能在内联后优化掉其中的 a==0 ? 部分。）
使用可用于 SHLX 的 BMI2 对其进行编译将使它在现代 Intel 上高效。
使用内联 asm 解决 Sandybridge-family 错过的优化
SnB-family 的变量计数移位比平常慢: cl=0，shl %cl, %reg 必须保留 FLAGS 不变。这是 "x86 tax" 的一部分，高性能 x86 CPUs 必须支付超标量乱序执行。）
AMD 显然将轮班管理为一个 uop，没有限制/惩罚。
因此 bts 到清零寄存器是实现 1ULL << count 的更好选择，尤其是在英特尔 CPUs 上，异或清零非常便宜，并且 bts reg,reg是单个 uop（而不是 Ryzen 上的 2 个）。
与@DavidWohlferd 的回答中的版本（基于我的评论）相比，这通过在 a==0 的情况下使用 a 作为零来保存指令，而不需要额外的归零寄存器.评论讨论性能影响。
#include <stdint.h>
#include <limits.h>
uint64_t LeadingBitIsolate_asm(uint64_t a)
{
uint64_t bit;
uint64_t bts_target = 0;
asm (
"BSR %[a], %[bit] \n\t" // ZF = (a==0)
"BTS %[bit], %[res] \n\t" // sets CF = old bit = 0 but not ZF
// possible partial-flag stall on some CPUs for reading ZF after writing CF
// but not SnB-family
"CMOVZ %[a], %[res]" // res = a (= 0) if BSR detected a==0
: [bit] "=r" (bit), [res] "+r"(bts_target) // no early clobber: input read before either output written
: [a] "r" (a)
: "cc" // redundant but not harmful on x86: flags clobber is always implied
);
return bts_target;
}
在 BTS 写入 CF 后读取 ZF 对于较旧的英特尔 CPUs 是危险的，它将导致 a partial-flag stall. See also
GCC 9.2 为我们提供了一个在 Skylake 上只有 4 微指令的序列。 (https://agner.org/optimize/)。异或归零需要前端微指令，但在 Sandybridge 系列上不需要后端执行单元（0 未融合域微指令）。
在 Haswell 和更早版本上是 5 微指令，其中 cmov 是 2 微指令/2c 延迟。既然你说你的 CPU 不支持 lzcnt，你可能有一个 IvyBridge 或更早的 (2 uop cmov)，或者一个旧的 AMD。
如果 input=0 预计很少发生或永远不会发生，那么分支可能是值得的， 特别是如果这是延迟的关键路径的一部分。特别是在较旧的 Intel 上，cmov 是 2 微指令。
gcc9.2 -O3 -mtune=skylake
LeadingBitIsolate_asm(unsigned long):
xorl %eax, %eax
BSR %rdi, %rdi
BTS %rdi, %rax
CMOVZ %rdi, %rax
ret
"rm"(a) 输入约束是可能的，但是
- 我们读了两遍所以最好让编译器载入寄存器一次
- clang 是愚蠢的，当它是一个选项时总是选择
m，即使这意味着溢出一个已经在寄存器中的值。 clang (LLVM) inline assembly - multiple constraints with useless spills / reloads bsr对现有 CPU 具有 "false" 依赖性，因此如果编译器碰巧为res和 [=37= 选择相同的寄存器会更好] 而不是写一个新的寄存器。如果以后不需要a，通常会发生这种情况。
BSR 并不是真正的错误依赖：如果输入为零，则目标保持不变。 AMD 甚至记录了这一点，但英特尔在离开 their documentation saying "undefined" contents.
的同时在他们的硬件中实现了它无论如何我们都无法利用这一点，我们有 65 种可能的输出，而 BTS 进入归零 reg 只能产生 64 种不同的输出。
您可能会想在保存 1 的寄存器上使用 rcl（循环进位），但首先 rcl %cl, %reg 非常慢，其次它仍然屏蔽& 63 的移位，因此它无法将 1 一直移位到 CF。
没有部分标志停顿，较旧的 Intel 上的关键路径更短
使用 BTC 并利用 BSR 零输入行为，我们可以制作一个版本，该版本可能在旧的 Intel P6 系列上更好，例如 Nehalem 和 Core 2（其中 cmov 是 2 微码，部分标志停顿是一个问题）。
虽然它不保存微指令，因为它需要一个额外的异或归零寄存器。它确实缩短了关键路径延迟，如果我们使用 test/setz 与 3-cycle-latency bsr 并行使用，而不是使用 BSR 的 ZF 输出，它可能会进一步缩短.或者，如果编译器已经对输入进行了数学计算，它可能已经适当地设置了 ZF。很遗憾，无法查询。
btc=补=翻转一点，而不是无条件设置。如果目标寄存器是 1 而不是 0，如果我们知道这种情况的位索引，那么这会产生零结果。
xor-zero / set flags / setcc 是标准惯用语，通常至少与 set flags / setcc / movzx 一样高效，因为 xor-zeroing 甚至比 movzx 更便宜，而且它不在延迟的关键路径上。 setcc 是所有 x86-64 CPUs 上的 1-uop 指令。
// depends on BSR behaviour that only AMD documents, but all real CPUs implement (for now?)
// it seems unlikely that this will change, though.
// The main advantage of this version is on P6-family and early Sandybridge
// where it definitely does work safely.
uint64_t LeadingBitIsolate_asm_p6(uint64_t a)
{
uint64_t btc_target;
uint64_t bit = 0;
//bool input_was_zero;
asm (
"xor %k[res], %k[res]\n\t" // make sure we avoid P6-family partial-reg stalls with setz + reading full reg by forcing xor-zeroing, not MOV
"bsr %[a], %[bit] \n\t" // bit=count or unmodified (if a==0)
"setz %b[res]\n\t" // res = (a==0)
"btc %[bit], %[res] \n\t" // flip a bit. For a==0, flips bit 0 which SETZ set to 1
: [bit] "+r" (bit), [res] "=&q"(btc_target) // q = reg accessible as low-8, like RAX has AL. Any x86-64 reg
// early-clobber: [res] is written before a, but [bit] isn't.
// ,"=@ccz" (input_was_zero) // optional GCC6 flag output. Or "=@ccc" to read from CF (btc result) and avoid partial-flag stalls
: [a] "r" (a)
: "cc"
);
return btc_target;
//return input_was_zero;
}
GCC9 和 t运行k 有一个奇怪的寄存器分配错过优化，它在 r8 中产生 res 并且必须 mov 它返回到 RAX。
gcc8.3 -O3 -mtune=nehalem
LeadingBitIsolate_asm_p6(unsigned long):
xorl %edx, %edx # compiler-generated
xor %eax, %eax # inline asm
bsr %rdi, %rdx
setz %al
btc %rdx, %rax
ret
在英特尔 CPU 上，如 Core2、Nehalem 和 Sandybridge 系列，这是 5 微指令，没有停顿。 BSR 有 3 个周期的延迟，其余的有 1 个周期的延迟。从 RDI 输入到 RAX 输出，延迟为 3 + 1 + 1 = 5 个周期。 （setz 必须等待 BSR 的输出。正如我上面提到的，在 bsr 之前 a 上的 test/setz 将允许指令级并行性，在 test 将关键路径延迟缩短另一个周期。）
在 AMD Bulldozer 系列 / Ryzen 上，因为 bsr 而贵得多。 setz 仍然是 1 微指令，btc 是 2 微指令。
在Atom/Silvermont，因为BSR也很贵
除非您使用 lzcnt 制作版本并执行 运行 时间调度或其他操作，否则没有解决慢速 BSR 的方法。 （可能对于 调用 这个函数的循环；调用开销可能仍然比在具有 8 到 10 uop bsr 的 CPU 上使用 bsr 更糟糕. 特别是 Ryzen 具有高 uop 吞吐量。)
这对于 a!=0 的情况非常有效，将 BTC 放入归零寄存器以翻转 BSR 找到的位索引处的位。
对于a==0情况：
# starting: rdx=rax=0
bsr %rdi, %rdx # leaves RDX=0 (unmodified) and sets ZF
setz %al # sets RAX=1
btc %rdx, %rax # flips bit 0 of RAX, changing it back to 0
# rax = 0 (result), rdx = 0 (bitpos)
当我在 C 中使用两个 "+r" 输入都设置为零时，GCC 决定异或零 EAX/RAX，但使用 mov %rax, %rdx 将其复制到 RDX！ （浪费 REX 前缀）。这在 Sandybridge 上显然更糟，它消除了异或归零但没有消除移动。不过，它在 AMD Ryzen 上更好，它具有 mov-elimination，但仍然需要一个用于异或归零的后端 uop。
用 mov 复制 0 与异或归零在 P6 系列（Core2 / Nehalem）上基本上是中性的，除了只有异或归零避免写入 AL 的部分寄存器停顿使用 setcc 并使用 btc 读取 RAX。所以我将异或归零放在内联 asm 中，以确保它实际上是异或归零，而不是 gcc 为 res 选择的 mov。 (
请注意，对于输入=0 的情况，BSR 保留目标未修改的行为 仅由 AMD 记录，未由 Intel 正式记录。但它 是 由所有英特尔的硬件实现的，至少是任何支持 64 位模式的硬件。关于 Via Nano 或古老的 Intel 的 IDK。