将两位数转换为低内存表示的最快方法
fastest way to convert two-bit number to low-memory representation
我有一个 56 位数字，可能有两个设置位，例如 00000000 00000000 00000000 00000000 00000000 00000000 00000011。换句话说，两个位分布在 56 位中，因此我们有 bin(56,2)=1540 个可能的排列。
我现在正在寻找一个这样的56位数字到11位数字的无损映射，可以携带2048因此也可以携带1540。知道结构，这个11位数字足以存储值我的低密度（个）56 位数字。
我想最大化性能（如果可能的话，这个函数应该每秒 运行 数百万甚至数十亿次）。到目前为止，我只提出了一些循环：
int inputNumber = 24; // 11000
int bitMask = 1;
int bit1 = 0, bit2 = 0;
for(int n = 0; n < 54; ++n, bitMask *= 2)
{
if((inputNumber & bitMask) != 0)
{
if(bit1 != 0)
bit1 = n;
else
{
bit2 = n;
break;
}
}
}
并使用这两位，我可以轻松生成最大 1540 个数字。
但是没有比使用这样的循环更快的版本了吗？
大多数 ISA 都有硬件支持 bit-scan 指令，该指令可以找到设置位的位置。 对于任何架构，使用它而不是简单的循环或 bithack你关心这个运行宁快。 https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious 有一些聊胜于无的技巧，但这些技巧仍然比单个有效的 asm 指令差得多。
但是 ISO C++ 不能移植公开 clz/ctz 操作；它只能通过内部函数/内置函数用于各种实现。 （并且 x86 intrinsincs 对 all-zero 输入有怪癖，对应于 asm 指令行为）。
对于某些 ISA，它是一个 count-leading-zeros 给你 31 - highbit_index。对于其他人，这是一个 CTZ 计数尾随零操作，为您提供低位的索引。 x86 两者都有。 （而且它的 high-bit 查找器实际上直接找到 high-bit 索引，而不是 leading-zero 计数，除非你使用 BMI1 lzcnt 而不是传统的 bsr） https://en.wikipedia.org/wiki/Find_first_set 有一个 table 不同的 ISA 有什么。
GCC 可移植地提供 __builtin_clz 和 __builtin_ctz；在没有硬件支持的 ISA 上，它们编译为对辅助函数的调用。 见What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C? and Implementation of __builtin_clz
（对于 64 位整数，您需要 long long 版本：如 __builtin_ctzll GCC manual。）
如果我们只有一个CLZ，用high=63-CLZ(n)和low= 63-CLZ((-n) & n)来隔离低位。请注意，x86 的 bsr 指令实际上产生 63-CLZ()，即 bit-index 而不是 leading-zero 计数。所以 63-__builtin_clzll(n) 可以在 x86 上编译成单条指令； IIRC gcc 确实注意到了这一点。或者 2 条指令，如果 GCC 使用额外的 xor-zeroing 来避免不方便的错误依赖。
如果我们只有CTZ，做low = CTZ(n)和high = CTZ(n & (n - 1))清除最低设置位。（保留高位，假设数字有恰好 2 个设置位）。
如果我们都有，low = CTZ(n) 和 high = 63-CLZ(n)。我不确定 GCC 在非 x86 ISA 上做了什么，因为它们不是本地可用的。 GCC 内置函数始终可用，即使针对没有它的硬件也是如此。但是内部实现不能使用上述技巧，因为它不知道总是恰好设置了 2 位。
（我写出了完整的公式；这个答案的早期版本在这部分中颠倒了 CLZ 和 CTZ。我发现这很容易发生在我身上，尤其是当我还必须跟踪 x86 的 bsr 和 bsr（位扫描反向和正向）并记住它们分别是前导和尾随。）
因此，如果您同时使用 CTZ 和 CLZ，您可能会以其中之一的缓慢仿真而告终。或者在 ARM 上使用 rbit 到 bit-reverse 的 clz 进行快速仿真，这是 100% 的。
AVX512CD 具有 SIMD VPLZCNTQ 64 位整数，因此您可以与最近的 Intel CPUs 并行编码 2、4 或 8x 64 位整数。对于 SSSE3 或 AVX2，您可以通过使用 pshufb _mm_shuffle_epi8 byte-shuffle 作为 4 位 LUT 并结合 _mm_max_epu8 来构建 SIMD lzcnt。最近有一个关于这个的问答，但我找不到它。 （它可能只适用于 16 位整数；更宽的需要更多的工作。）
有了这个，一旦考虑到打包结果的吞吐量成本，Skylake-X 或 Cascade Lake CPU 可能会每 2 或 3 个时钟周期压缩 8 个 64 位整数。 SIMD 对于将 12 位或 11 位结果打包成连续的比特流当然很有用，例如使用 variable-shift 说明，如果这是您想要对结果执行的操作。在大约 3 或 4GHz 的时钟速度下，单线程可能使您每个时钟超过 100 亿次。但前提是输入来自连续内存。根据您要对结果执行的操作，可能会花费更多的周期来完成更多工作，而不仅仅是将它们打包成 16 位整数。例如打包成比特流。但是 SIMD 应该有利于 variable-shift 指令，这些指令可以将每个寄存器的 11 或 12 位排列到正确的位置，以便在洗牌后一起进行或运算。
编码效率和编码性能之间存在折衷。将 12 位用于两个 6 位索引（位位置）压缩和解压缩都非常简单，至少在具有 bit-scan 指令的硬件上是这样。
或者代替 bit-indices，一个或两个可以是 leading 零计数 ，因此解码将是 (1ULL << 63) >> a. 1ULL>>63 是一个固定常量，您实际上可以 right-shift，或者编译器可以将其转换为 1ULL << (63-a) 的 left-shift，IIRC 在汇编中将其优化为 1 << (-a)像 x86 这样的 ISA，其中移位指令屏蔽了移位计数（只看低 6 位）。
此外，2x 12 位是整数字节，但 11 位只能为每 8 个输出提供整数字节（如果您正在打包它们）。因此索引 bit-packed 数组更简单。
0 仍然是一个特例：可以使用 all-ones bit-indices 来处理（即索引 = 位 63，在低 56 位之外）。在 decode/decompress 上，设置 2 位位置 (1ULL<<a) | (1ULL<<b)，然后设置 & 掩码以清除高位。或者偏置你的位索引并解码右移 1.
如果我们不必处理零，那么现代 x86 CPU 如果不需要执行任何其他操作，则每秒可以执行 1 或 20 亿次编码。例如对于 bit-scan 指令，Skylake 每个时钟有 1 个吞吐量，并且应该能够以每 2 个时钟编码 1 个数字，这只是瓶颈所在。 （或者使用 SIMD 可能更好）。只需 4 条标量指令，我们就可以得到低索引和高索引（64 位 tzcnt + bsr），移位 6 位，然后一起或。1 或者在 AMD 上，避免 bsr / bsf 并手动执行 63-lzcnt.
对 input == 0 进行分支或无分支检查以将最终结果设置为任何 hard-coded 常量（如 63 , 63）应该很便宜。
在 AArch64 等其他 ISA 上进行压缩也很便宜。它有 clz 但没有 ctz。可能你最好的选择是使用一个内在的 rbit 到 bit-reverse 一个数字（所以 bit-reversed 数字上的 clz 直接给你 bit-index低位。现在是反转版本的高位。）假设 rbit 与 add / sub 一样快，这比使用多条指令清除低位更便宜。
如果你真的想要 11 位，那么你需要避免 2x 6 位的冗余能够让一个索引大于另一个。就像可能有 6 位 a 和 5 位 b，并且 a<=b 意味着一些特殊的东西，比如 b+=32。我还没有完全考虑清楚。您需要能够对寄存器顶部或底部附近的 2 个相邻位进行编码，或者如果我们考虑像 56 位旋转一样在边界处换行，则 2 个设置位可能相距 28 位。
Melpomene 关于隔离低位和高位设置的建议可能作为其他内容的一部分很有用，但仅适用于在只有一个 bit-scan 方向可用而不是两个方向可用的目标上进行编码。即使这样，您实际上也不会使用 both 表达式。 Leading-zero计数不需要你隔离低位，你只需要清除它就可以得到高位。
脚注 1：在 x86 上解码也很便宜：x |= (1<<a) 是 1 条指令：bts。但是许多编译器错过了优化并且没有注意到这一点，而是实际上移动了 1。 bts reg, reg 自 PPro 以来在 Intel 上是 1 uop / 1 周期延迟，或者在 AMD 上有时是 2 uops。 （只有内存目标版本慢。）https://agner.org/optimize/
AMD CPUs 上的最佳编码性能需要 BMI1 tzcnt / lzcnt 因为 bsr 和 bsf 较慢（6 微指令而不是 1 https://agner.org/optimize/).在 Ryzen 上，lzcnt 是 1 uop，1c 延迟，每个时钟吞吐量 4。但是 tzcnt 是 2 微码。
对于 BMI1，编译器可以使用 blsr 清除寄存器的最低设置位（并复制它）。即现代 x86 有一个 dst = (SRC-1) bitwiseAND ( SRC ); 的指令，在 Intel 上是 single-uop 但在 AMD 上是 2 uops。
但是在 AMD Ryzen 上 lzcnt 比 tzcnt 更高效，AMD 最好的 asm 可能不使用它。
或者可能是这样的（假设正好是 2 位，显然我们可以做到）。
(这个 asm 是你想让你的编译器发出的。实际上不要使用内联 asm！)
Ryzen_encode_scalar: ; input in RDI, output in EAX
lzcnt rcx, rdi ; 63-high bit index
tzcnt rdx, rdi ; low bit
mov eax, 63
sub eax, ecx
shl edx, 6
or eax, edx ; (low_bit << 6) | high_bit
ret ; goes away with inlining.
移动低 bit-index 平衡关键路径的长度，允许更好的 instruction-level 并行性， 如果我们需要 63-CLZ高位.
吞吐量：总共 7 微指令，没有 execution-unit 瓶颈。所以在每个时钟流水线宽度 5 微指令下，这比每 2 个时钟 1 微指令要好。
Skylake_encode_scalar: ; input in RDI, output in EAX
tzcnt rax, rdi ; low bit. No false dependency on Skylake. GCC will probably xor-zero RAX because there is on Broadwell and earlier.
bsr rdi, rdi ; high bit index. same,same reg avoids false dep
shl eax, 6
or eax, edx
ret ; goes away with inlining.
这从输入到输出有 5 个周期的延迟：位扫描指令在 Intel 上是 3 个周期，在 AMD 上是 1 个周期。 SHL+OR各加1个周期。
对于吞吐量，我们每个周期只有一个 bit-scan 瓶颈（执行端口 1），因此我们可以每 2 个周期进行一次编码，并留出 4 微码 front-end 带宽用于负载，存储和循环开销（或其他），假设我们有多个独立的编码要做。
（但对于多个独立编码的情况，如果存在廉价的 vplzcntq 仿真并且数据来自内存，则 SIMD 对于 AMD 和 Intel 可能仍然更好。）
标量解码可以是这样的：
decode: ;; input in EDI, output in RAX
xor eax, eax ; RAX=0
bts rax, rdi ; RAX |= 1ULL << (high_bit_idx & 63)
shr edi, 6 ; extract low_bit_idx
bts rax, rdi ; RAX |= 1ULL << low_bit_idx
ret
这有 3 个班次（包括 bts），在 Skylake 上只能在端口 0 或端口 6 上 运行。所以在 Intel 上，front-end 只需要 4 微指令（所以每个时钟 1 微指令作为做其他事情的一部分）。但是，如果仅 这样做，它会在每 1.5 个时钟周期解码 1 次时成为移位吞吐量的瓶颈。
在 4GHz CPU 上，每秒解码 26.66 亿次，所以是的，我们很好地达到了您的目标:)
或 Ryzen，bts reg,reg 是 2 uops ，吞吐量为 0.5c，但 shr 可以 运行 在任何端口上。所以它不会从 bts 窃取吞吐量，整个过程是 6 微秒（相对于 Ryzen 的流水线在最窄处是 5 宽）。所以每 1.2 个时钟周期进行 1 次编码，只是 front-end 成本的瓶颈。
有 BMI2 可用性le，从寄存器中的 1 开始并使用 shlx rax, rbx, rdi 可以用单个 uop 替换 xor-zeroing + 第一个 BTS，假设寄存器中的 1 可以在一个循环。
（此优化完全取决于您的编译器；flag-less 移位只是 copy-and-shift 的更有效方法，可用于 -march=haswell 或 -march=znver1，或其他具有 BMI2 的目标。）
无论哪种方式，您都将编写 retval = 1ULL << (packed & 63) 来解码第一位。但是，如果您想知道哪些编译器在这里编写了漂亮的代码，这就是您要找的。
我有一个 56 位数字，可能有两个设置位，例如 00000000 00000000 00000000 00000000 00000000 00000000 00000011。换句话说，两个位分布在 56 位中，因此我们有 bin(56,2)=1540 个可能的排列。
我现在正在寻找一个这样的56位数字到11位数字的无损映射，可以携带2048因此也可以携带1540。知道结构，这个11位数字足以存储值我的低密度（个）56 位数字。
我想最大化性能（如果可能的话，这个函数应该每秒 运行 数百万甚至数十亿次）。到目前为止，我只提出了一些循环：
int inputNumber = 24; // 11000
int bitMask = 1;
int bit1 = 0, bit2 = 0;
for(int n = 0; n < 54; ++n, bitMask *= 2)
{
if((inputNumber & bitMask) != 0)
{
if(bit1 != 0)
bit1 = n;
else
{
bit2 = n;
break;
}
}
}
并使用这两位，我可以轻松生成最大 1540 个数字。
但是没有比使用这样的循环更快的版本了吗？
大多数 ISA 都有硬件支持 bit-scan 指令，该指令可以找到设置位的位置。 对于任何架构，使用它而不是简单的循环或 bithack你关心这个运行宁快。 https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious 有一些聊胜于无的技巧，但这些技巧仍然比单个有效的 asm 指令差得多。
但是 ISO C++ 不能移植公开 clz/ctz 操作；它只能通过内部函数/内置函数用于各种实现。 （并且 x86 intrinsincs 对 all-zero 输入有怪癖，对应于 asm 指令行为）。
对于某些 ISA，它是一个 count-leading-zeros 给你 31 - highbit_index。对于其他人，这是一个 CTZ 计数尾随零操作，为您提供低位的索引。 x86 两者都有。 （而且它的 high-bit 查找器实际上直接找到 high-bit 索引，而不是 leading-zero 计数，除非你使用 BMI1 lzcnt 而不是传统的 bsr） https://en.wikipedia.org/wiki/Find_first_set 有一个 table 不同的 ISA 有什么。
GCC 可移植地提供 __builtin_clz 和 __builtin_ctz；在没有硬件支持的 ISA 上，它们编译为对辅助函数的调用。 见What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C? and Implementation of __builtin_clz
（对于 64 位整数，您需要 long long 版本：如 __builtin_ctzll GCC manual。）
如果我们只有一个CLZ，用high=63-CLZ(n)和low= 63-CLZ((-n) & n)来隔离低位。请注意，x86 的 bsr 指令实际上产生 63-CLZ()，即 bit-index 而不是 leading-zero 计数。所以 63-__builtin_clzll(n) 可以在 x86 上编译成单条指令； IIRC gcc 确实注意到了这一点。或者 2 条指令，如果 GCC 使用额外的 xor-zeroing 来避免不方便的错误依赖。
如果我们只有CTZ，做low = CTZ(n)和high = CTZ(n & (n - 1))清除最低设置位。（保留高位，假设数字有恰好 2 个设置位）。
如果我们都有，low = CTZ(n) 和 high = 63-CLZ(n)。我不确定 GCC 在非 x86 ISA 上做了什么，因为它们不是本地可用的。 GCC 内置函数始终可用，即使针对没有它的硬件也是如此。但是内部实现不能使用上述技巧，因为它不知道总是恰好设置了 2 位。
（我写出了完整的公式；这个答案的早期版本在这部分中颠倒了 CLZ 和 CTZ。我发现这很容易发生在我身上，尤其是当我还必须跟踪 x86 的 bsr 和 bsr（位扫描反向和正向）并记住它们分别是前导和尾随。）
因此，如果您同时使用 CTZ 和 CLZ，您可能会以其中之一的缓慢仿真而告终。或者在 ARM 上使用 rbit 到 bit-reverse 的 clz 进行快速仿真，这是 100% 的。
AVX512CD 具有 SIMD VPLZCNTQ 64 位整数，因此您可以与最近的 Intel CPUs 并行编码 2、4 或 8x 64 位整数。对于 SSSE3 或 AVX2，您可以通过使用 pshufb _mm_shuffle_epi8 byte-shuffle 作为 4 位 LUT 并结合 _mm_max_epu8 来构建 SIMD lzcnt。最近有一个关于这个的问答，但我找不到它。 （它可能只适用于 16 位整数；更宽的需要更多的工作。）
有了这个，一旦考虑到打包结果的吞吐量成本，Skylake-X 或 Cascade Lake CPU 可能会每 2 或 3 个时钟周期压缩 8 个 64 位整数。 SIMD 对于将 12 位或 11 位结果打包成连续的比特流当然很有用，例如使用 variable-shift 说明，如果这是您想要对结果执行的操作。在大约 3 或 4GHz 的时钟速度下，单线程可能使您每个时钟超过 100 亿次。但前提是输入来自连续内存。根据您要对结果执行的操作，可能会花费更多的周期来完成更多工作，而不仅仅是将它们打包成 16 位整数。例如打包成比特流。但是 SIMD 应该有利于 variable-shift 指令，这些指令可以将每个寄存器的 11 或 12 位排列到正确的位置，以便在洗牌后一起进行或运算。
编码效率和编码性能之间存在折衷。将 12 位用于两个 6 位索引（位位置）压缩和解压缩都非常简单，至少在具有 bit-scan 指令的硬件上是这样。
或者代替 bit-indices，一个或两个可以是 leading 零计数 ，因此解码将是 (1ULL << 63) >> a. 1ULL>>63 是一个固定常量，您实际上可以 right-shift，或者编译器可以将其转换为 1ULL << (63-a) 的 left-shift，IIRC 在汇编中将其优化为 1 << (-a)像 x86 这样的 ISA，其中移位指令屏蔽了移位计数（只看低 6 位）。
此外，2x 12 位是整数字节，但 11 位只能为每 8 个输出提供整数字节（如果您正在打包它们）。因此索引 bit-packed 数组更简单。
0 仍然是一个特例：可以使用 all-ones bit-indices 来处理（即索引 = 位 63，在低 56 位之外）。在 decode/decompress 上，设置 2 位位置 (1ULL<<a) | (1ULL<<b)，然后设置 & 掩码以清除高位。或者偏置你的位索引并解码右移 1.
如果我们不必处理零，那么现代 x86 CPU 如果不需要执行任何其他操作，则每秒可以执行 1 或 20 亿次编码。例如对于 bit-scan 指令，Skylake 每个时钟有 1 个吞吐量，并且应该能够以每 2 个时钟编码 1 个数字，这只是瓶颈所在。 （或者使用 SIMD 可能更好）。只需 4 条标量指令，我们就可以得到低索引和高索引（64 位 tzcnt + bsr），移位 6 位，然后一起或。1 或者在 AMD 上，避免 bsr / bsf 并手动执行 63-lzcnt.
对 input == 0 进行分支或无分支检查以将最终结果设置为任何 hard-coded 常量（如 63 , 63）应该很便宜。
在 AArch64 等其他 ISA 上进行压缩也很便宜。它有 clz 但没有 ctz。可能你最好的选择是使用一个内在的 rbit 到 bit-reverse 一个数字（所以 bit-reversed 数字上的 clz 直接给你 bit-index低位。现在是反转版本的高位。）假设 rbit 与 add / sub 一样快，这比使用多条指令清除低位更便宜。
如果你真的想要 11 位，那么你需要避免 2x 6 位的冗余能够让一个索引大于另一个。就像可能有 6 位 a 和 5 位 b，并且 a<=b 意味着一些特殊的东西，比如 b+=32。我还没有完全考虑清楚。您需要能够对寄存器顶部或底部附近的 2 个相邻位进行编码，或者如果我们考虑像 56 位旋转一样在边界处换行，则 2 个设置位可能相距 28 位。
Melpomene 关于隔离低位和高位设置的建议可能作为其他内容的一部分很有用，但仅适用于在只有一个 bit-scan 方向可用而不是两个方向可用的目标上进行编码。即使这样，您实际上也不会使用 both 表达式。 Leading-zero计数不需要你隔离低位，你只需要清除它就可以得到高位。
脚注 1：在 x86 上解码也很便宜：x |= (1<<a) 是 1 条指令：bts。但是许多编译器错过了优化并且没有注意到这一点，而是实际上移动了 1。 bts reg, reg 自 PPro 以来在 Intel 上是 1 uop / 1 周期延迟，或者在 AMD 上有时是 2 uops。 （只有内存目标版本慢。）https://agner.org/optimize/
AMD CPUs 上的最佳编码性能需要 BMI1 tzcnt / lzcnt 因为 bsr 和 bsf 较慢（6 微指令而不是 1 https://agner.org/optimize/).在 Ryzen 上，lzcnt 是 1 uop，1c 延迟，每个时钟吞吐量 4。但是 tzcnt 是 2 微码。
对于 BMI1，编译器可以使用 blsr 清除寄存器的最低设置位（并复制它）。即现代 x86 有一个 dst = (SRC-1) bitwiseAND ( SRC ); 的指令，在 Intel 上是 single-uop 但在 AMD 上是 2 uops。
但是在 AMD Ryzen 上 lzcnt 比 tzcnt 更高效，AMD 最好的 asm 可能不使用它。
或者可能是这样的（假设正好是 2 位，显然我们可以做到）。
(这个 asm 是你想让你的编译器发出的。实际上不要使用内联 asm！)
Ryzen_encode_scalar: ; input in RDI, output in EAX
lzcnt rcx, rdi ; 63-high bit index
tzcnt rdx, rdi ; low bit
mov eax, 63
sub eax, ecx
shl edx, 6
or eax, edx ; (low_bit << 6) | high_bit
ret ; goes away with inlining.
移动低 bit-index 平衡关键路径的长度，允许更好的 instruction-level 并行性， 如果我们需要 63-CLZ高位.
吞吐量：总共 7 微指令，没有 execution-unit 瓶颈。所以在每个时钟流水线宽度 5 微指令下，这比每 2 个时钟 1 微指令要好。
Skylake_encode_scalar: ; input in RDI, output in EAX
tzcnt rax, rdi ; low bit. No false dependency on Skylake. GCC will probably xor-zero RAX because there is on Broadwell and earlier.
bsr rdi, rdi ; high bit index. same,same reg avoids false dep
shl eax, 6
or eax, edx
ret ; goes away with inlining.
这从输入到输出有 5 个周期的延迟：位扫描指令在 Intel 上是 3 个周期，在 AMD 上是 1 个周期。 SHL+OR各加1个周期。
对于吞吐量，我们每个周期只有一个 bit-scan 瓶颈（执行端口 1），因此我们可以每 2 个周期进行一次编码，并留出 4 微码 front-end 带宽用于负载，存储和循环开销（或其他），假设我们有多个独立的编码要做。
（但对于多个独立编码的情况，如果存在廉价的 vplzcntq 仿真并且数据来自内存，则 SIMD 对于 AMD 和 Intel 可能仍然更好。）
标量解码可以是这样的：
decode: ;; input in EDI, output in RAX
xor eax, eax ; RAX=0
bts rax, rdi ; RAX |= 1ULL << (high_bit_idx & 63)
shr edi, 6 ; extract low_bit_idx
bts rax, rdi ; RAX |= 1ULL << low_bit_idx
ret
这有 3 个班次（包括 bts），在 Skylake 上只能在端口 0 或端口 6 上 运行。所以在 Intel 上，front-end 只需要 4 微指令（所以每个时钟 1 微指令作为做其他事情的一部分）。但是，如果仅 这样做，它会在每 1.5 个时钟周期解码 1 次时成为移位吞吐量的瓶颈。
在 4GHz CPU 上，每秒解码 26.66 亿次，所以是的，我们很好地达到了您的目标:)
或 Ryzen，bts reg,reg 是 2 uops ，吞吐量为 0.5c，但 shr 可以 运行 在任何端口上。所以它不会从 bts 窃取吞吐量，整个过程是 6 微秒（相对于 Ryzen 的流水线在最窄处是 5 宽）。所以每 1.2 个时钟周期进行 1 次编码，只是 front-end 成本的瓶颈。
有 BMI2 可用性le，从寄存器中的 1 开始并使用 shlx rax, rbx, rdi 可以用单个 uop 替换 xor-zeroing + 第一个 BTS，假设寄存器中的 1 可以在一个循环。
（此优化完全取决于您的编译器；flag-less 移位只是 copy-and-shift 的更有效方法，可用于 -march=haswell 或 -march=znver1，或其他具有 BMI2 的目标。）
无论哪种方式，您都将编写 retval = 1ULL << (packed & 63) 来解码第一位。但是，如果您想知道哪些编译器在这里编写了漂亮的代码，这就是您要找的。