将所有位从最低有效位翻转到最重要的最后 1 位值的最有效方法是什么？
what is the most efficient way to flip all the bits from the least significant bit up to the most significant last 1 bit value?
例如我有一个 uint8_t 可以是任何值，我只想翻转从最低有效位到最高有效最后 1 位值的所有位？我将如何以最有效的方式做到这一点？有没有可以避免使用循环的解决方案？
以下是一些案例：
左侧是原始位 - 翻转后的右侧。
00011101 -> 0000001000000000 -> 0000000011111111 -> 0000000011110111 -> 0000100001000000 -> 00111111
[编辑]
类型也可以大于uint8_t，可以是uint32_t、uint64_t和__uint128_t。我只使用 uint8_t，因为它是示例中最容易显示的尺寸。
一般来说，我希望大多数解决方案大致具有以下形式：
- 计算需要翻转的位掩码
- 通过该掩码异或
如评论中所述，x64 是一个感兴趣的目标，在 x64 上，您可以像这样执行第 1 步：
- 找到最重要的 1 的基于 1 的位置
p，通过前导零 (_lzcnt_u64) 并从 64（或 32，以适当者为准）中减去它。
- 使用从最低有效位开始的
p 个连续设置位创建一个掩码，可能使用 _bzhi_u64。
有一些变体，例如使用 BitScanReverse 找到最重要的 1（但它有一个丑陋的零案例），或者使用移位而不是 bzhi（但它有一个丑陋的案例64). lzcnt 和 bzhi 是一个很好的组合，没有丑陋的案例。 bzhi 需要 BMI2（Intel Haswell 或更新版本，AMD Zen 或更新版本）。
放在一起：
x ^ _bzhi_u64(~(uint64_t)0, 64 - _lzcnt_u64(x))
可以进一步简化为
_bzhi_u64(~x, 64 - _lzcnt_u64(x))
如彼得所示。这不遵循最初的两步计划，而是翻转 所有 位，然后重置最初为前导零的位。
由于那些原始的前导零在 ~x 中形成连续的前导 1 序列，bzhi 的替代方法可能是将适当的 2 的幂添加到 ~x（尽管有时零，这可能被认为是 264，将设置的位放在数字的顶部之外）。不幸的是，我们需要的 2 的幂计算起来有点烦人，至少我想不出一个好的方法，这对我来说似乎是死胡同。
第 1 步也可以使用一些移位和按位 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 CPU 的 BSR 较慢（但 LZCNT 速度较快；https://uops.info/），因此您可能需要 uint8_t 或 uint16_t 的 shift/or 版本（其中花费最少的步骤），特别是如果您需要与所有 CPU 兼容 和 AMD 上的速度比英特尔上的更重要。
此通用版本在 SIMD 元素中也很有用，尤其是窄元素，在 AVX-512 之前我们没有 leading-zero-count。
这是一个 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），我们可以避免对 n==0 的额外检查， 和 我们使用的是允许计数为 32 的班次。（在 C 中，type-width 或更大的班次是未定义的行为。在 x86 上，实际上班次计数被屏蔽 &31 除了 64 -位，所以这可以用于 uint16_t 或 uint8_t 使用 uint32_t 掩码。）
注意避免 C 未定义的行为，包括关于 __builtin_clz 输入为 0 的任何假设；现代 C 编译器不是可移植的汇编器，尽管有时我们希望它们是可移植的，因为语言不能移植地公开我们想要利用的 CPU 特性。例如，clang 假定 __builtin_clz(n) 不能为 32，即使将其编译为 lzcnt.
详情见。
如果您的用例是 performance-critical，您可能还需要考虑使用 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 位示例（注意：您可能需要点击组装窗格底部的刷新按钮才能将其显示到 re-compile 和 运行 如果您在输出窗格中看到“返回的程序：139”——这似乎是由于当前 Compiler Explorer 中的一个故障。
TL:DR：在为具有 lzcnt 的 64 位机器（AMD 自 K10，Intel 自 Haswell）编译时，使用 uint64_t 移位以使用 uint32_t 高效实施。没有 lzcnt（只有 bsr 这是 x86 的基线）n==0 情况仍然很特殊。
对于 uint64_t 版本，困难的部分是最高设置位有 65 个不同的可能位置，包括 non-existent （lzcnt 在所有位为零时生成 64 ).但是在 x86 上使用 64 位 operand-size 的单个移位只能产生 64 个不同值中的一个（假设输入不变），因为 x86 移位屏蔽了像 foo >> (c&63)
这样的计数
使用班次需要 special-casing 一个 leading-bit-position，通常是 n==0 的情况。正如哈罗德的回答所示，BMI2 bzhi 避免了这种情况，允许从 0..64.
开始计数
32 位 operand-size 移位相同：它们屏蔽 c&31。 但是要为 uint32_t 生成掩码，我们可以在 x86-64 上有效地使用 64 位移位。（或 32 位用于 uint16_t 和 uint8_t。有趣的事实：使用 8 位或 16 位 operand-size 的 x86 asm 移位仍然掩盖了它们的计数 mod 32，因此它们甚至可以在不使用更宽的 operand-size 的情况下移出所有位. 但是 32 位操作数大小是有效的，不需要乱用 partial-register 写。）
对于比寄存器宽度窄的类型，此策略比 bzhi 更有效。
// 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 144=]). 但不是 uint64_t（您可以使用 unsigned __int128 班次，但 shrd 掩盖了其班次计数 mod 64 所以编译器仍然需要一些条件行为来模拟它。所以你不妨手动执行 cmov 或其他操作，或 sbb same,same 以在 a 中生成 0 或 -1注册为要移动的掩码。）
Godbolt 使用 gcc 和 clang。请注意，将 _lzcnt_u32 替换为 __builtin_clz 是不安全的； clang11 和后来的假设即使将其编译为 lzcnt 指令 1 也无法产生 32，并将移位 operand-size 优化为 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），我们得到相同的 code-gen 除了 shr rax, cl。这些 CPU 仍然有 lzcnt，否则无法编译。
（我很好奇 Intel Skylake Pentium/Celeron 运行 lzcnt 是 lzcnt 还是 bsf。他们缺少 BMI1/BMI2，但是lzcnt 有自己的功能标志。
似乎 low-power 最近的 Tremont uarches 不见了 lzcnt，不过，根据 InstLatx64 for a Pentium Silver N6005 Jasper Lake-D, Tremont core. I didn't manually look for the feature bit in the raw CPUID dumps of recent Pentium/Celeron, but Instlat 的说法，如果有人想检查的话，确实有可用的。）
无论如何，bzhi 也需要 BMI2，因此如果您要与 uint64_t 以外的任何尺寸进行比较，这就是比较。
此 shrx 版本可以在循环中的寄存器中保持其 -1 不变。因此，如果编译器有备用寄存器，则 mov reg,-1 可以在内联后提升到循环之外。最好的 bzhi 策略不需要掩码常量，因此它没有任何好处。 _bzhi_u64(~x, 64 - _lzcnt_u64(x)) 是 5 微指令，但适用于 64 位机器上的 64 位整数。其延迟关键路径长度与此相同。 (lzcnt/sub/bzhi).
如果没有 LZCNT，一个选项可能是始终翻转作为为 CMOV 设置 FLAGS 的一种方式，并使用 -1 << bsr(n) 将其中一些异或返回到原始状态。这可以减少关键路径延迟。 IDK 如果可以诱使 C 编译器发出它。特别是如果你想利用这样一个事实，即如果源为零，真正的 CPU 会保持 BSR 目标不变，但只有 AMD 记录了这一事实。 （英特尔表示这是一个“未定义”的结果。）
（TODO：完成此 hand-written asm 想法。）
uint64_t 案例的其他 C 想法：cmov 或 cmp/sbb（生成 0 或 -1）与 [=14 并行=] 缩短关键路径延迟？看看我玩那个的 Godbolt link。
ARM/AArch64 使它们的移位计数饱和，这与 x86 掩码标量的方式不同。如果可以安全地利用它（没有 C shift-count UB）那将是整洁的，允许像这样的东西。
x86 SIMD 移位也使它们的计数饱和，Paul R 使用 vlzcnt 和 variable-shift 通过 AVX-512 答案利用了这一点。 （尽管如此，将数据复制到 XMM reg 并返回一个标量偏移是不值得的；仅当您有多个元素要执行时才有用。）
脚注 1：使用 __builtin_clz 或 ...ll
的 clang codegen
使用 __builtin_clzll(n) 将使 clang 使用 64 位 operand-size 进行移位，因为从 32 到 63 的值成为可能。但是如果没有 lzcnt，你实际上不能用它来为 CPU 编译。如果没有可用的 lzcnt，编译器将使用的 63-bsr 不会产生我们在这种情况下需要的 64。除非您在 bsr 之前执行 n<<=1; / n|=1; 或其他操作并调整结果，否则不会比 cmov.
慢
如果您使用的是 64 位 lzcnt，您需要 uint64_t mask = -1ULL，因为在 zero-extending 到 uint64_t 之后会有 32 个额外的前导零。幸运y all-ones 在所有 ISA 上实现起来相对便宜，所以使用它而不是 0xffffffff00000000ULL
例如我有一个 uint8_t 可以是任何值，我只想翻转从最低有效位到最高有效最后 1 位值的所有位？我将如何以最有效的方式做到这一点？有没有可以避免使用循环的解决方案？
以下是一些案例：
左侧是原始位 - 翻转后的右侧。
00011101->0000001000000000->0000000011111111->0000000011110111->0000100001000000->00111111
[编辑]
类型也可以大于uint8_t，可以是uint32_t、uint64_t和__uint128_t。我只使用 uint8_t，因为它是示例中最容易显示的尺寸。
一般来说，我希望大多数解决方案大致具有以下形式：
- 计算需要翻转的位掩码
- 通过该掩码异或
如评论中所述，x64 是一个感兴趣的目标，在 x64 上，您可以像这样执行第 1 步：
- 找到最重要的 1 的基于 1 的位置
p，通过前导零 (_lzcnt_u64) 并从 64（或 32，以适当者为准）中减去它。 - 使用从最低有效位开始的
p个连续设置位创建一个掩码，可能使用_bzhi_u64。
有一些变体，例如使用 BitScanReverse 找到最重要的 1（但它有一个丑陋的零案例），或者使用移位而不是 bzhi（但它有一个丑陋的案例64). lzcnt 和 bzhi 是一个很好的组合，没有丑陋的案例。 bzhi 需要 BMI2（Intel Haswell 或更新版本，AMD Zen 或更新版本）。
放在一起：
x ^ _bzhi_u64(~(uint64_t)0, 64 - _lzcnt_u64(x))
可以进一步简化为
_bzhi_u64(~x, 64 - _lzcnt_u64(x))
如彼得所示。这不遵循最初的两步计划，而是翻转 所有 位，然后重置最初为前导零的位。
由于那些原始的前导零在 ~x 中形成连续的前导 1 序列，bzhi 的替代方法可能是将适当的 2 的幂添加到 ~x（尽管有时零，这可能被认为是 264，将设置的位放在数字的顶部之外）。不幸的是，我们需要的 2 的幂计算起来有点烦人，至少我想不出一个好的方法，这对我来说似乎是死胡同。
第 1 步也可以使用一些移位和按位 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 CPU 的 BSR 较慢（但 LZCNT 速度较快；https://uops.info/），因此您可能需要 uint8_t 或 uint16_t 的 shift/or 版本（其中花费最少的步骤），特别是如果您需要与所有 CPU 兼容 和 AMD 上的速度比英特尔上的更重要。
此通用版本在 SIMD 元素中也很有用，尤其是窄元素，在 AVX-512 之前我们没有 leading-zero-count。
这是一个 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），我们可以避免对 n==0 的额外检查， 和 我们使用的是允许计数为 32 的班次。（在 C 中，type-width 或更大的班次是未定义的行为。在 x86 上，实际上班次计数被屏蔽 &31 除了 64 -位，所以这可以用于 uint16_t 或 uint8_t 使用 uint32_t 掩码。）
注意避免 C 未定义的行为，包括关于 __builtin_clz 输入为 0 的任何假设；现代 C 编译器不是可移植的汇编器，尽管有时我们希望它们是可移植的，因为语言不能移植地公开我们想要利用的 CPU 特性。例如，clang 假定 __builtin_clz(n) 不能为 32，即使将其编译为 lzcnt.
详情见
如果您的用例是 performance-critical，您可能还需要考虑使用 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 位示例（注意：您可能需要点击组装窗格底部的刷新按钮才能将其显示到 re-compile 和 运行 如果您在输出窗格中看到“返回的程序：139”——这似乎是由于当前 Compiler Explorer 中的一个故障。
TL:DR：在为具有 lzcnt 的 64 位机器（AMD 自 K10，Intel 自 Haswell）编译时，使用 uint64_t 移位以使用 uint32_t 高效实施。没有 lzcnt（只有 bsr 这是 x86 的基线）n==0 情况仍然很特殊。
对于 uint64_t 版本，困难的部分是最高设置位有 65 个不同的可能位置，包括 non-existent （lzcnt 在所有位为零时生成 64 ).但是在 x86 上使用 64 位 operand-size 的单个移位只能产生 64 个不同值中的一个（假设输入不变），因为 x86 移位屏蔽了像 foo >> (c&63)
使用班次需要 special-casing 一个 leading-bit-position，通常是 n==0 的情况。正如哈罗德的回答所示，BMI2 bzhi 避免了这种情况，允许从 0..64.
32 位 operand-size 移位相同：它们屏蔽 c&31。 但是要为 uint32_t 生成掩码，我们可以在 x86-64 上有效地使用 64 位移位。（或 32 位用于 uint16_t 和 uint8_t。有趣的事实：使用 8 位或 16 位 operand-size 的 x86 asm 移位仍然掩盖了它们的计数 mod 32，因此它们甚至可以在不使用更宽的 operand-size 的情况下移出所有位. 但是 32 位操作数大小是有效的，不需要乱用 partial-register 写。）
对于比寄存器宽度窄的类型，此策略比 bzhi 更有效。
// 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 144=]). 但不是 uint64_t（您可以使用 unsigned __int128 班次，但 shrd 掩盖了其班次计数 mod 64 所以编译器仍然需要一些条件行为来模拟它。所以你不妨手动执行 cmov 或其他操作，或 sbb same,same 以在 a 中生成 0 或 -1注册为要移动的掩码。）
Godbolt 使用 gcc 和 clang。请注意，将 _lzcnt_u32 替换为 __builtin_clz 是不安全的； clang11 和后来的假设即使将其编译为 lzcnt 指令 1 也无法产生 32，并将移位 operand-size 优化为 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），我们得到相同的 code-gen 除了 shr rax, cl。这些 CPU 仍然有 lzcnt，否则无法编译。
（我很好奇 Intel Skylake Pentium/Celeron 运行 lzcnt 是 lzcnt 还是 bsf。他们缺少 BMI1/BMI2，但是lzcnt 有自己的功能标志。
似乎 low-power 最近的 Tremont uarches 不见了 lzcnt，不过，根据 InstLatx64 for a Pentium Silver N6005 Jasper Lake-D, Tremont core. I didn't manually look for the feature bit in the raw CPUID dumps of recent Pentium/Celeron, but Instlat 的说法，如果有人想检查的话，确实有可用的。）
无论如何，bzhi 也需要 BMI2，因此如果您要与 uint64_t 以外的任何尺寸进行比较，这就是比较。
此 shrx 版本可以在循环中的寄存器中保持其 -1 不变。因此，如果编译器有备用寄存器，则 mov reg,-1 可以在内联后提升到循环之外。最好的 bzhi 策略不需要掩码常量，因此它没有任何好处。 _bzhi_u64(~x, 64 - _lzcnt_u64(x)) 是 5 微指令，但适用于 64 位机器上的 64 位整数。其延迟关键路径长度与此相同。 (lzcnt/sub/bzhi).
如果没有 LZCNT，一个选项可能是始终翻转作为为 CMOV 设置 FLAGS 的一种方式，并使用 -1 << bsr(n) 将其中一些异或返回到原始状态。这可以减少关键路径延迟。 IDK 如果可以诱使 C 编译器发出它。特别是如果你想利用这样一个事实，即如果源为零，真正的 CPU 会保持 BSR 目标不变，但只有 AMD 记录了这一事实。 （英特尔表示这是一个“未定义”的结果。）
（TODO：完成此 hand-written asm 想法。）
uint64_t 案例的其他 C 想法：cmov 或 cmp/sbb（生成 0 或 -1）与 [=14 并行=] 缩短关键路径延迟？看看我玩那个的 Godbolt link。
ARM/AArch64 使它们的移位计数饱和，这与 x86 掩码标量的方式不同。如果可以安全地利用它（没有 C shift-count UB）那将是整洁的，允许像这样的东西。
x86 SIMD 移位也使它们的计数饱和，Paul R 使用 vlzcnt 和 variable-shift 通过 AVX-512 答案利用了这一点。 （尽管如此，将数据复制到 XMM reg 并返回一个标量偏移是不值得的；仅当您有多个元素要执行时才有用。）
脚注 1：使用 __builtin_clz 或 ...ll
的 clang codegen
使用 __builtin_clzll(n) 将使 clang 使用 64 位 operand-size 进行移位，因为从 32 到 63 的值成为可能。但是如果没有 lzcnt，你实际上不能用它来为 CPU 编译。如果没有可用的 lzcnt，编译器将使用的 63-bsr 不会产生我们在这种情况下需要的 64。除非您在 bsr 之前执行 n<<=1; / n|=1; 或其他操作并调整结果，否则不会比 cmov.
如果您使用的是 64 位 lzcnt，您需要 uint64_t mask = -1ULL，因为在 zero-extending 到 uint64_t 之后会有 32 个额外的前导零。幸运y all-ones 在所有 ISA 上实现起来相对便宜，所以使用它而不是 0xffffffff00000000ULL