例如，我有一个uint8_t，它可以是任何值，而我只想将所有位从最低有效位向上翻转到最高有效的最后1位值？我该如何以最有效的方式做到这一点？，有没有一种解决方案可以避免使用循环？
以下是一些案例：
左侧是原始位-翻转后的右侧。
00011101->0000001000000000->0000000011111111->0000000011110111->0000100001000000->00111111
[EDIT]
该类型也可以大于uint8_t，可以是uint32_t、uint64_t和__uint128_t。我只是使用uint8_t，因为它是在示例案例中最容易显示的大小。
一般来说，我预计大多数解决方案的形式大致如下：
- 计算需要翻转的位的掩码
- 通过该掩码进行XOR
如评论中所述，x64是感兴趣的目标，在x64上，您可以这样做步骤1：
- 通过前导零(
_lzcnt_u64)并从64(或32，以适当者为准)中减去零，找到最高有效1的基于1的位置p - 创建一个掩码，其中
p连续设置位从最低有效位开始，可能使用_bzhi_u64
有一些变化，例如使用BitScanReverse来查找最有效的1(但它对零的情况很糟糕)，或者使用移位代替bzhi(但对64的情况很难看)。CCD_ 22和CCD_。bzhi需要BMI2(Intel Haswell或更新版本，AMD Zen或更新版本)。
把它放在一起：
x ^ _bzhi_u64(~(uint64_t)0, 64 - _lzcnt_u64(x))
可以进一步简化为
_bzhi_u64(~x, 64 - _lzcnt_u64(x))
如Peter所示。这并没有遵循最初的两步计划，相反，所有位都被翻转，然后最初为零的位被重置。
由于这些原始的前导零在~x中形成了前导1的连续序列，因此bzhi的一个替代方案可以是将适当的2的幂加到~x上(尽管有时为零，这可能被认为是264，将设置位刚好放在数字的顶部之外)。不幸的是，我们需要的二次幂的计算有点烦人，至少我不能想出一个好的方法来做，这对我来说似乎是一条死胡同
步骤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的此转换/或版本(步骤最少)，特别是如果您需要与所有CPU兼容，并且AMD上的速度比Intel上的更重要。
这个通用版本在SIMD元素中也很有用，尤其是在窄元素中，在AVX-512之前我们没有前导零计数。
TL:DR：在为具有lzcnt的64位机器(AMD自K10起，Intel自Haswell起)进行编译时，使用uint64_t移位来高效地实现uint32_t。没有lzcnt(只有bsr是x86的基线)，n==0的情况仍然很特殊。
对于uint64_t版本，最困难的部分是最高设置位有65个不同的可能位置，包括不存在的位置(当所有位为零时，lzcnt产生64)。但是，x86上64位操作数大小的单次移位只能产生64个不同值中的一个(假设输入为常量)，因为x86移位像foo >> (c&63)一样屏蔽了计数
使用移位需要特殊情况下的一个前导位位置，通常为n==0情况。正如Harold的回答所示，BMI2bzhi避免了这种情况，允许从0..64开始的位计数。
32位操作数大小移位也是如此：它们屏蔽c&31但是要为uint32_t生成掩码，我们可以在x86-64上高效地使用64位移位。
对于比寄存器宽度窄的类型，此策略甚至比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)但不是uint64_t(您可以使用unsigned __int128移位，但shrd屏蔽了其移位计数mod 64，因此编译器仍然需要一些条件行为来模拟它。因此，您还可以手动执行cmov或其他操作，或sbb same,same在寄存器中生成0或-1作为要移位的掩码。)
Godbolt带有gcc和clang。请注意，用__builtin_clz替换_lzcnt_u32是不安全的；clang11和后来的假设即使将其编译为lzcnt指令1也不能产生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有自己的功能标志。不过，根据InstLatx64的Pentium Silver N6005 Jasper Lake-D，Tremont内核的说法，像Tremont这样的低功耗uars似乎缺少lzcnt。我没有在最近的Pentium/Celeron的原始CPUID转储中手动查找功能位，但如果有人想检查，Instlat确实有这些功能位。)
无论如何，bzhi也需要BMI2，所以如果你将其与除uint64_t之外的任何尺寸的BMI2进行比较，这就是比较。
这个shrx版本可以在循环之间的寄存器中保持其-1恒定。因此，如果编译器有一个备用寄存器，那么mov reg,-1可以在内联后从循环中提升出来。最好的bzhi策略不需要掩码常数，因此它没有任何好处。_bzhi_u64(~x, 64 - _lzcnt_u64(x))是5个uops，但适用于64位机器上的64位整数。它的延迟关键路径长度与此相同。(lzcnt/sub/bzhi)。
如果没有LZCNT，一种选择可能是始终翻转，作为为CMOV设置FLAGS的一种方式，并使用-1 << bsr(n)对其中一些进行异或，使其恢复到原始状态。这可以减少关键路径延迟。IDK，如果可以诱使C编译器发出这个。尤其是如果你想利用这样一个事实，即如果源为零，那么真正的CPU会保持BSR目的地不变，但只有AMD记录了这一事实。(英特尔称这是一个"未定义"的结果。)
(TODO:完成这个手写的asm想法。)
uint64_t情况的其他C想法：cmov或cmp/sbb(生成0或-1)与lzcnt并行以缩短关键路径延迟？看看我玩的Godbolt链接。
ARM/AArch64使它们的移位计数饱和，这与x86为标量掩码的方式不同。如果一个人可以安全地利用这一点(没有C移位计数UB)，那将是整洁的，允许像这样好的东西。
x86SIMD移位也使它们的计数饱和，Paul R利用了这一点，使用vlzcnt和可变移位的AVX-512回答。(不过，不值得将数据复制到XMM reg并返回一个标量移位；只有当您有多个元素要做时才有用。)
脚注1:__builtin_clz或...ll的clang codegen
使用__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，因为在零之后将有32个额外的前导零扩展到uint64_t。幸运的是，在所有ISAs上实现所有这些都相对便宜，所以使用它而不是0xffffffff00000000ULL
这里有一个32位int的简单示例，它可以与gcc和兼容的编译器(clang等人)一起使用，并且可以在大多数体系结构中移植。
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，因此使用uint32_t掩码，这可以用于uint16_t或uint8_t。)
注意避免C未定义的行为，包括对输入为0的__builtin_clz的任何假设；现代的C编译器不是可移植的汇编程序，尽管我们有时希望它们是可移植的，因为语言不能移植地暴露我们想要利用的CPU功能。例如，clang假设__builtin_clz(n)即使在编译为lzcnt时也不能是32。
有关详细信息，请参阅@PeterCordes的回答。
如果您的用例对性能至关重要，您可能还需要考虑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);
}
}
这使用了与其他解决方案相同的方法，即计数前导零、创建掩码、XOR，但对于32位元素，它每次循环迭代处理8个元素。您可以类似地实现它的64位版本，但不幸的是，对于元素大小<32位或>64位。
您可以在编译器资源管理器上看到上面的32位示例(注意：如果您在输出窗格中得到"返回的程序：139"，您可能需要点击程序集窗格底部的刷新按钮才能重新编译并运行它——这似乎是由于当前编译器资源管理程序中的一个小故障造成的)。