将所有位从最低有效位翻转到最高有效最后 1 位值的最有效方法是什么？

Question

举例来说，我有一个uint8_t可以是任何值的值，而我只想将所有位从最低有效位翻转到最高有效的最后 1 位值？我该如何以最有效的方式做到这一点？有没有一种解决方案可以避免使用循环？

以下是一些案例：

左边是原来的位，右边是翻转后的位。

• 00011101->00000010
• 00000000->00000000
• 11111111->00000000
• 11110111->00001000
• 01000000->00111111

[编辑]

该类型也可以大于uint8_t，也可以是uint32_t，uint64_t和__uint128_t。我只是使用它uint8_t，因为它是示例案例中最容易显示的尺寸。

Answer 1

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

1. 计算需要翻转的位掩码
2. 通过该掩码进行异或

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

• p通过前导零 ( _lzcnt_u64) 并从 64（或 32，以合适的为准）中减去该值，找到最高有效 1 的从 1 开始的位置。
• 创建一个具有p从最低有效位开始的连续设置位的掩码，可能使用_bzhi_u64.

有一些变体，例如使用 BitScanReverse 查找最高有效的 1（但对于 0 的情况很丑陋），或者使用移位代替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))

正如彼得所示。这并不遵循最初的两步计划，而是翻转所有位，然后重置最初为前导零的位。

由于那些原始的前导零形成了 中前导 1 的连续序列~x，替代方案bzhi可以是将 2 的适当幂添加到~x（尽管有时是零，这可能被认为是 2 ⁶⁴，将设置位刚好超出 的顶部）号码）。不幸的是，我们需要的 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_tor uint16_t（需要最少的步骤），特别是如果您需要与所有 CPU 兼容并提高速度AMD 比 Intel 更重要。

这个通用版本在 SIMD 元素中也很有用，尤其是窄元素，在 AVX-512 之前我们没有前导零计数。