logo标签列表

如何最有效地翻转从最低位到最高位最后一个1之间所有的比特位？

cx86bit-manipulationbit-shiftbitmask
5
举个例子，假设我有一个可取任何值的uint8_t，我想要翻转所有比特位，从最低有效比特位翻转到最高有效的最后一个1比特位？如何以最有效的方式实现？是否有一种解决方案可以避免使用循环？
以下是一些情况：
左边是原始比特位，右边是翻转后的结果。
  • 00011101 -> 00000010
  • 00000000 -> 00000000
  • 11111111 -> 00000000
  • 11110111 -> 00001000
  • 01000000 -> 00111111
[编辑] 类型也可能比uint8_t更大，可能是uint32_t、uint64_t和__uint128_t。我只是使用uint8_t因为它是在示例用例中最容易显示的大小。
5
定义“高效”。什么度量？uint8_t只有256个值，因此您可以使用查找表。 - kaylum
特定架构或可移植解决方案？ - Paul R
@PaulR 目前我正在开发一个 x86_64 平台，所以可能会选择 x86_64。 - 0xdeadbeef
如果你有一种快速计算前导零的方法，那么剩下的就很容易了。 - user3386109
@user3386109 是的，但是 x ^ (ones >> lzcnt(x)) 的简单解决方案不起作用（如果 x = 0 则失败），因此其余部分也很有趣。 - harold
显示剩余2条评论
4个回答
6

一般来说，我预计大多数解决方案的形式大致如下：

  1. 计算需要翻转的位的掩码
  2. 使用该掩码进行异或操作

如评论中所述，x64是一个感兴趣的目标，在x64上，您可以像这样执行步骤1：

  • 通过前导零（_lzcnt_u64）找到最高位1的基于1的位置 p，并从64（或适当的32）中减去。
  • 创建一个掩码，其从最低有效位开始具有p个连续设置的位，可能使用_bzhi_u64。

还有一些变化，例如使用BitScanReverse来查找最高位1（但它对于0有一个丑陋的情况），或者使用移位而不是bzhi（但它对于64有一个丑陋的情况）。lzcnt和bzhi是没有丑陋情况的良好组合。 bzhi需要BMI2（英特尔Haswell或更高版本，AMD Zen或更高版本）。

将它们组合在一起：

x ^ _bzhi_u64(~(uint64_t)0, 64 - _lzcnt_u64(x))

这可以进一步简化为

_bzhi_u64(~x,  64 - _lzcnt_u64(x))

正如Peter所示。这不遵循原始的2步计划，而是翻转了所有位，然后重置原来前导零的位。

由于那些原来的前导零在~x中形成了一系列连续的前导1，因此bzhi的替代方法可以是向~x添加适当的二次幂（尽管有时为零，可能被认为是264，将设置位放在数字顶部之外）。不幸的是，我们需要计算的二次幂有点麻烦，至少我想不出一个好方法来做到这一点，对我来说似乎是走投无路。

第一步也可以通过几次移位和按位OR的通用方式实现（没有特殊操作），如下所示：

// Get all-ones below the leading 1
// On x86-64, this is probably slower than Paul R's method using BSR and shift
//   even though you have to special case x==0
m = x | (x >> 1);
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
m |= m >> 32;  // last step should be removed if x is 32-bit

AMD处理器的BSR操作速度较慢（但LZCNT操作速度快；https://uops.info/），因此你可能需要使用这个移位或版本来处理uint8_t或uint16_t（在这些类型上的步骤最少），特别是如果你需要兼容所有的处理器，并且AMD上的速度比Intel更重要。

这个通用版本在SIMD元素中也很有用，特别是狭窄的元素，在AVX-512之前没有前导零计数。

似乎我没有_bzhi_u64指令，但是你提供的替代方案可行。 - 0xdeadbeef
1
@kabibesadagat，除非你真的必须这样做（6个移位OR步骤并不是很好，也不是很糟糕，但并不是很好），否则你可能不应该使用那种“通用”的方式。只要处理好边缘情况，你仍然可以使用移位来替换BZHI。 - harold
2
@kabibesadagat：在x86 CPU上，你永远不需要“通用”版本的m = x | (x>>1)。你总是至少有__builtin_clzll或等效物，它最坏情况下可以编译成BSR指令，因此你需要特殊处理零。或者在32位模式下，在两个半部分上使用两个BSR指令和其他检查。但无论如何，如果没有bzhi部分，则需要替换，而不是lzcnt部分。 - Peter Cordes
@harold: _bzhi_u64(~x, 64 - _lzcnt_u64(x)) 可以避免需要一个常数“-1”，这样可以节省一两个指令，具体取决于编译器。 https://godbolt.org/z/edqMf5GMa 未翻转的位都是零。 - Peter Cordes
4

TL:DR：在编译支持lzcnt的64位机器时，使用uint64_t移位以实现与uint32_t的高效配合。对于没有lzcnt（只有基线bsr的x86），n==0情况仍然很特殊。

对于uint64_t版本，难点在于最高位的65种不同可能位置，包括不存在的情况（当所有位都为零时lzcnt产生64）。但是，在x86上使用64位操作数大小的单个移位只能产生64个不同的值之一（假设输入为常量），因为x86移位像foo >> (c&63)这样掩码计数。

使用移位需要特殊处理一个前导位位置，通常是n==0的情况。正如Harold的回答所示，BMI2 bzhi避免了这种情况，允许位数从0到64。

对于32位操作数大小的移位操作，它们会掩码c&31。但是为了生成uint32_t的掩码，我们可以在x86-64上高效地使用64位移位。(或者对于uint16_t和uint8_t使用32位移位。有趣的事实是：x86汇编使用8或16位操作数大小进行移位仍然会掩码其计数模32，因此它们可以移出所有位而无需使用更宽的操作数大小。但32位操作数大小是高效的，不需要处理部分寄存器写入。)这种策略甚至比对于小于寄存器宽度的类型使用更有效。

// optimized for 64-bit mode, otherwise 32-bit bzhi or a cmov version of Paul R's is good

#ifdef __LZCNT__
#include <immintrin.h>
uint32_t flip_32_on_64(uint32_t n)
{
    uint64_t mask32 = 0xffffffff;  // (uint64_t)(uint32_t)-1u32
    // this needs to be _lzcnt_u32, not __builtin_clz; we need 32 for n==0
    // If lznct isn't available, we can't avoid handling n==0  zero specially
    uint32_t mask = mask32 >> _lzcnt_u32(n);
    return n ^ mask;
}
#endif

这同样适用于 uint8_t 和 uint16_t（使用相同掩码的完全相同代码，在零扩展后对它们使用32位lzcnt）。但是不适用于 uint64_t（您可以使用 unsigned __int128 移位，但 shrd 模 64 地掩盖其移位计数，因此编译器仍然需要一些条件行为来模拟它。所以最好手动执行cmov或者 sbb same,same 以生成一个在寄存器中作为掩码进行移位的 0 或 -1。） Godbolt使用gcc和clang。请注意，将_lzcnt_u32替换为__builtin_clz是不安全的；clang11及更高版本假定即使将其编译为lzcnt指令，也无法产生32，会将移位操作数大小优化为32，这将作为mask32 >> clz(n) & 31。
# clang 14 -O3 -march=haswell  (or znver1 or bdver4 or other BMI2 CPUs)
flip_32_on_64:
        lzcnt   eax, edi           # skylake fixed the output false-dependency for lzcnt/tzcnt, but not popcnt.  Clang doesn't care, it's reckless about false deps except inside a loop in a single function.
        mov     ecx, 4294967295
        shrx    rax, rcx, rax
        xor     eax, edi
        ret

如果没有BMI2，例如使用-march=bdver1或barcelona（也称为k10），我们得到与shr rax, cl相同的代码生成。这些CPU仍然具有lzcnt，否则这将无法编译。

（我想知道英特尔Skylake Pentium / Celeron是否将lzcnt作为lzcnt或bsf运行。它们缺少BMI1 / BMI2，但lzcnt具有自己的功能标志。看起来最近的Tremont之类的低功耗uarches缺少lzcnt，但根据 InstLatx64 for a Pentium Silver N6005 Jasper Lake-D，Tremont core  显示。我没有手动查找最近的Pentium / Celeron的原始CPUID转储中的特征位，但Instlat提供了这些信息，如果有人想要检查。）

无论如何，bzhi 还需要 BMI2，因此如果你对除了 uint64_t 以外的任何大小进行比较，这就是比较。这个 shrx 版本可以在循环中保留其 -1 常量。因此，在内联后，如果编译器有多余的寄存器，mov reg,-1 可以被提升到循环外。最好的 bzhi 策略不需要掩码常量，因此它无法获得任何优势。对于 64 位机器上的 64 位整数，_bzhi_u64(~x, 64 - _lzcnt_u64(x)) 是 5 个 uops，但其延迟关键路径长度与此相同。（lzcnt/sub/bzhi）。
没有LZCNT指令，一个选项可能是始终进行翻转以获取设置FLAGS的方式，然后使用-1 << bsr(n)将其中一些异或回原始状态。这可以减少关键路径延迟。不知道C编译器是否能够发出此命令。特别是如果您想利用真实CPU保持BSR目标不变（如果源为零），但只有AMD记录了这一事实。（英特尔表示这是“未定义”的结果。）
（待办事项：完成这个手写的asm想法。）
其他针对uint64_t情况的C语言想法：并行使用cmov或cmp/sbb（生成0或-1），以及lzcnt以缩短关键路径延迟。请参阅我正在尝试的Godbolt链接。

ARM/AArch64会对其移位计数进行饱和，不像x86标量掩码。如果能够安全地利用这一点（没有C移位计数UB），那将是很好的，可以实现与此相当的效果。

x86 SIMD移位也会饱和它们的计数器，Paul R利用了这一点，使用vlzcnt和变量移位来回答AVX-512问题。（但是，只有在有多个元素需要处理时才有用；如果只有一个标量移位，则不值得将数据复制到XMM寄存器中再返回。）

注1：带有__builtin_clz或...ll的clang代码生成

使用__builtin_clzll(n)将会让clang使用64位操作数大小进行移位，因为32到63的值变得可能。但是你不能在没有lzcnt的CPU上使用它来编译。一个编译器在没有lzcnt可用时使用的63-bsr将不会产生我们需要的64。除非你在bsr之前做了n<<=1; / n|=1;或者其他一些调整结果的操作，但这比cmov慢。
如果您正在使用64位lzcnt，则希望uint64_t mask = -1ULL，因为在零扩展为uint64_t后会有32个额外的前导零。幸运的是，在所有ISA上实现全1相对较便宜，因此请使用它，而不是0xffffffff00000000ULL。
1
Clang 11+ 对于 32 位移位的奇怪行为难道不是由于 __builtin_clz 在零时未定义，因此它认为 32 不是可能的移位计数吗？如果我在那里使用 _lzcnt_u64 或 __builtin_clzll，这个问题就会消失。 - harold
@harold：啊，就是这个问题。是的，今天重新回到这个问题时我意识到需要使用lzcnt而不是__builtin_clz，后者会使用bsr，但我没有更新Godbolt链接，并且没有深入考虑clang代码生成的影响。谢谢。 - Peter Cordes
3

以下是针对32位整数的简单示例，适用于gcc及兼容编译器（clang et al），并且几乎在大多数体系结构上都可以移植。

uint32_t flip(uint32_t n)
{
    if (n == 0) return 0;
    uint32_t mask = ~0U >> __builtin_clz(n);
    return n ^ mask;
}

演示

如果我们在x86-64上使用lzcnt（或ARM上的clz），并且我们使用了允许计数为32的移位，那么我们就可以避免n==0的额外检查。（在C语言中，类型宽度或更大的移位是未定义的行为。在x86上，实际上除了64位之外的移位会掩码&31，因此这可以用于uint16_t或uint8_t，使用一个uint32_t掩码。）

要注意避免C语言中的未定义行为，包括对输入为0的__builtin_clz的任何假设；现代C编译器不是可移植的汇编程序，即使我们有时候希望它们是，当语言没有可移植地暴露我们想要利用的CPU特性时。例如，clang假定__builtin_clz(n)不能为32，即使它将其编译为lzcnt也是如此。

有关详细信息，请参见@PeterCordes的答案。

2
非常类似于Harold的BMI解决方案，我会期望如此。上述方法的一个优点是它在大多数/所有架构上都是可移植的，因为编译器将使用目标平台上__builtin_clz的最有效指令序列。 - Paul R
1
这是有道理的，可以通过在“-1U >> clz”之后执行mask = (n == 0 ? 0 : mask);来使其无分支。对于64位，请使用__builtin_clzll。使用BMI2进行有效移位，它可以编译得更加高效。 - Peter Cordes
1
如果你在64位机器上只使用32位整数，你可以使用0xffffffffULL >> _lzcnt_u32(n)来将所有位移出去，如果前导零计数为32的话。(而不是在x86 / x86-64上将移位数掩码为0的32位移位。)ARM/AArch64会饱和移位计数，因此如果有一种C语言表达方式可以实现这一点，我们可能可以获得clz和移位操作，而无需对全宽寄存器进行零检查。 - Peter Cordes
1
不要仅仅使用-mlzcnt！同时使用-march=haswell，以启用BMI1和BMI2，在英特尔上实现高效的变量计数移位，并且不需要使用CL进行计数。（AMD K10及更高版本具有lzcnt，但仅Zen具有BMI2。也不包括冰湖之前的奔腾/赛扬）。https://godbolt.org/z/Ej4GYxxec。嗯，看起来在clang 11及更高版本中存在clang代码生成错误，我的(uint64_t)-1u32 >> clz想法仅使用32位操作数大小。但是，正确编译时，它只有4条指令加上一个ret。（如果为Haswell而不是Skylake进行适当调整，则为5，打破lzcnt的输出依赖性。） - Peter Cordes
1
（顺便说一句，我自己写了这个答案。） - Peter Cordes
显示剩余5条评论
2

如果您的使用场景对性能要求很高，您可能还需要考虑使用SIMD实现来处理大量元素的位翻转操作。以下是一个使用AVX512处理32位元素的示例：

void flip(const uint32_t in[], uint32_t out[], size_t n)
{
    assert((n & 7) == 0); // for this example we only handle arrays which are vector multiples in size
    for (size_t i = 0; i + 8 <= n; i += 8)
    {
        __m512i vin = _mm512_loadu_si512(&in[i]);
        __m512i vlz = _mm512_lzcnt_epi32(vin);
        __m512i vmask = _mm512_srlv_epi32(_mm512_set1_epi32(-1), vlz);
        __m512i vout = _mm512_xor_si512(vin, vmask);
        _mm512_storeu_si512(&out[i], vout);
    }
}

这个解决方案与其他解决方案采用相同的方法，即计算前导零、创建掩码、进行异或运算，但对于32位元素，它每次循环迭代处理8个元素。您可以类似地实现一个64位版本，但不幸的是，对于小于32位或大于64位的元素大小，没有类似的AVX512内部函数。 您可以在Compiler Explorer上看到上述32位示例的操作（注意：如果输出窗格中出现“程序返回：139”，则可能需要点击汇编窗格底部的刷新按钮以重新编译和运行 - 这似乎是由于Compiler Explorer目前存在故障）。
2
哦，不错，这个很好。因为x86 SIMD移位饱和它们的计数（所以它们可以将所有位移出），而标量移位则掩盖它，以便它环绕。 （与ISO C移位不同，其中uint32_t >> 32仅仅是未定义的行为。） - Peter Cordes
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接