我有一个 56 位数字，可能有两个设置位，例如00000000 00000000 00000000 00000000 00000000 00000000 00000011.换句话说，两个位分布在 56 位之间，因此我们有bin(56,2)=1540可能的排列。
我现在寻找这样一个 56 位数字到一个可以携带 2048 的 11 位数字的无损映射，因此也可以携带 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 都支持查找设置位位置的位扫描指令。使用它而不是朴素的循环或 bithack 对于您关心快速运行的任何架构。 https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious 有一些技巧总比没有好，但这些技巧仍然比单个有效的 asm 指令差得多。
但是ISO C++不能移植地公开clz/ctz操作;它只能通过内部函数/内置来实现各种实现。 (x86 内部函数具有全零输入的怪癖，对应于 asm 指令行为)。
对于某些 ISA，它是一个计数前导零，为您提供31 - highbit_index. 对于其他人，这是一个CTZ计数尾随零操作，为您提供低位的索引。 x86 两者兼而有之。 (它的高位查找器实际上直接找到高位索引，而不是前导零计数，除非您使用 BMI1lzcnt而不是传统的bsr)https://en.wikipedia.org/wiki/Find_first_set 有一个不同 ISA 具有的表格。
GCC可移植地提供__builtin_clz和__builtin_ctz;在没有硬件支持的ISA上，它们编译为对帮助程序函数的调用。请参阅在 C 中的整数中查找最高设置位 (msb) 的最快/最有效的方法是什么？和实施__builtin_clz
(对于 64 位整数，您需要long long版本：如__builtin_ctzllGCC 手册。
如果我们只有一个CLZ，请使用high=63-CLZ(n)和low= 63-CLZ((-n) & n)来隔离低位。 注意x86的bsr指令实际上产生63-CLZ()，即位索引而不是前导零计数。 所以63-__builtin_clzll(n)可以在 x86 上编译为一条指令;IIRC gcc确实注意到了这一点。 或者 2 条指令，如果 GCC 使用额外的异或归零来避免不方便的错误依赖。
如果我们只有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位反转clz，这是100%好的。
AVX512CD 具有针对 64 位整数的 SIMDVPLZCNTQ，因此您可以对 2、4 或 8 个 64 位整数进行并行编码，并与最新的英特尔 CPU 上的整数并行编码。 对于 SSSE3 或 AVX2，您可以通过将字节洗牌pshufb_mm_shuffle_epi8用作 4 位 LUT 并与_mm_max_epu8结合使用来构建 SIMD lzcnt。最近有一个关于这个的问答，但我找不到它。 (它可能仅适用于 16 位整数;更宽需要更多工作。
有了这个，Skylake-X或Cascade Lake CPU可以每2或3个时钟周期压缩8x 64位整数，一旦你考虑到打包结果的吞吐量成本。 SIMD 对于将 12 位或 11 位结果打包到连续比特流中当然很有用，例如，如果您想对结果执行可变移位指令。 在~3或4GHz的时钟速度下，单线程每个时钟可能会超过100亿。 但前提是输入来自连续内存。 根据您要对结果执行的操作，除了将它们打包为 16 位整数之外，还可能需要花费更多周期才能完成更多操作。 例如，打包到比特流中。 但 SIMD 应该适合于此，具有可变移位指令，可以将每个寄存器的 11 或 12 位排列到正确的位置，以便在洗牌后将 OR 排列在一起。
编码效率和编码性能之间存在权衡。 将 12 位用于两个 6 位索引(位位置)压缩和解压缩都非常简单，至少在具有位扫描指令的硬件上是这样。
或者代替位索引，一个或两个都可以引导零计数，因此解码将是(1ULL << 63) >> a。1ULL>>63是一个固定常数，您实际上可以右移，或者编译器可以将其转换为1ULL << (63-a)的左移，IIRC对其进行优化以在x86等ISA的汇编中1 << (-a)，其中移位指令屏蔽了移位计数(仅查看低6位)。
此外，2x 12 位是整数字节，但 11 位只能为您提供每 8 个输出的整数字节，如果您要打包它们。 因此，索引位打包数组更简单。
0 仍然是一个特例：也许通过使用全 1 位索引来处理它(即索引 = 位 63，它超出了低 56 位)。 在解码/解压缩时，您将 2 位位置设置为(1ULL<<a) | (1ULL<<b)然后&掩码以清除高位。 或者偏置您的位索引并让右移解码 1。
如果我们不必处理零，那么现代 x86 CPU 如果不需要做任何其他事情，每秒可以执行 1 或 20 亿次编码。 例如，Skylake对于位扫描指令的每个时钟吞吐量为1个，并且应该能够以每2个时钟1个数字进行编码，只是瓶颈。 (或者使用 SIMD 可能更好)。 只需 4 条标量指令，我们就可以获得低索引和高索引(64 位tzcnt+bsr)，移位 6 位，以及一起 OR。1或者在AMD上，避免bsr/bsf并手动执行63-lzcnt。
不过，input == 0将最终结果设置为任何硬编码常量(如63 , 63)的分支或无分支检查应该很便宜。
其他 ISA (如 AArch64)上的压缩也很便宜。 它有clz，但没有ctz. 可能你最好的选择是使用一个内在的rbit来位反转一个数字(所以clz位反转的数字直接给你低位的位索引。 现在是反转版本的高位。 假设rbit的速度与add/sub一样快，这比使用多个指令清除低位便宜。
如果你真的想要 11 位，那么你需要避免 2x 6 位的冗余，能够让一个索引大于另一个索引。 比如可能有 6 位a和 5 位b，并且a<=b意味着像b+=32这样特殊的东西。 我还没有完全考虑清楚这一点。 您需要能够在寄存器的顶部或底部附近对 2 个相邻位进行编码，或者如果我们考虑像 56 位旋转一样在边界处包装，则 2 个设置位可能相距 28 位。
Melpomene关于隔离低集和高集位的建议可能作为其他内容的一部分有用，但仅适用于只有一个位扫描方向的目标上的编码，而不是两个方向。 即便如此，您实际上也不会同时使用这两个表达式。 前导零计数不需要您隔离低位，您只需要清除它即可获得高位。
脚注1：在x86上解码也很便宜：x |= (1<<a)是1指令：bts。 但是许多编译器错过了优化并且没有注意到这一点，而是实际上转移了1。 自 PPro 以来，英特尔bts reg, reg1 uop/1 周期延迟，有时在 AMD 上为 2 uops。 (只有内存目标版本很慢。 https://agner.org/optimize/
AMD CPU 上的最佳编码性能需要 BMI1tzcnt/lzcnt，因为bsr和bsf速度较慢(6 uops 而不是 1 https://agner.org/optimize/)。 在锐龙上，lzcnt是 1 uop、1c 延迟、每时钟吞吐量 4 个。 但tzcnt是 2 uops。
使用BMI1，编译器可以使用blsr清除寄存器的最低设置位(并复制它)。 即现代 x86 对在英特尔上是单 uop 但在 AMD 上为 2 uops 的dst = (SRC-1) bitwiseAND ( SRC );有一条指令。
但是由于lzcnt比AMD Ryzen上的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.
移动低位索引可以平衡关键路径的长度，从而允许更好的指令级并行性，如果我们需要63-CLZ高位。
吞吐量：总共 7 uops，没有执行单元瓶颈。 因此，在每个时钟管道宽度 5 uops 时，这比每 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 个周期延迟：位扫描指令在英特尔上为 3 个周期，而在 AMD 上为 1 个周期。 SHL + 或每个添加 1 个周期。
对于吞吐量，我们每个周期只设置一个位扫描(执行端口 1)的瓶颈，因此我们可以每 2 个周期执行一次编码，剩余 4 uop 前端带宽用于加载、存储和循环开销(或其他东西)，假设我们有多个独立的编码要做。
(但对于多个独立编码的情况，如果存在廉价的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 上运行。 因此，在英特尔上，前端只需花费 4 uops(因此作为执行其他操作的一部分，每个时钟 1 个)。 但是，如果只这样做，则每 1.5 个时钟周期 1 次解码就会成为移位吞吐量的瓶颈。
在 4GHz CPU 上，每秒解码 26.66 亿次，所以是的，我们很好地达到了您的目标:)
或者 Ryzen，bts reg,reg是 2 uops ，吞吐量为 0.5c，但shr可以在任何端口上运行。 所以它不会从bts窃取吞吐量，整个事情是 6 uops(而 Ryzen 的管道在最窄处是 5 宽)。 因此，每 1.2 个时钟周期 1 个编码，只是前端成本的瓶颈。
在 BMI2 可用的情况下，假设寄存器中的1可以在循环中重复使用，则从寄存器中的1开始并使用shlx rax, rbx, rdi可以用单个 uop 替换异或归零 + 第一个 BTS。
(这种优化完全取决于你的编译器来查找;无标志移位只是更有效的复制和移位方法，可用于-march=haswell或-march=znver1，或其他具有BMI2的目标。
无论哪种方式，您都只需编写retval = 1ULL << (packed & 63)来解码第一位。 但是，如果您想知道哪些编译器在这里制作了不错的代码，这就是您正在寻找的。