设置任意大小整数的前导零位 C++

Question

我想在标准 C++ 中将任何大小整数的前导零位设置为 1。

例如。

0001 0011 0101 1111 -> 1111 0011 0101 1111

我发现执行此操作的所有算法都需要相当昂贵的前导零计数。然而，这很奇怪。有非常快速且简单的方法来执行其他类型的位操作，例如：

 int y = -x & x; //Extracts lowest set bit, 1110 0101 -> 0000 0001

 int y = (x + 1) & x; //Will clear the trailing ones, 1110 0101 - > 1110 0100

 int y = (x - 1) | x; //Will set the trailing zeros, 0110 0100 - > 0110 0111

因此，这让我认为必须有一种方法可以在由基本位运算符组成的一行简单代码中设置整数的前导零。请告诉我还有希望，因为现在我正在准备反转整数中的位顺序，然后使用设置尾随零的快速方法，然后再次反转整数以将前导零设置为 1。这实际上比使用前导零计数要快得多，但与上面的其他算法相比仍然相当慢。

 template<typename T>
 inline constexpr void reverse(T& x)
 {
    T rev = 0;
    size_t s = sizeof(T) * CHAR_BIT;

    while(s > 0)
    {
        rev = (rev << 1) | (x & 0x01);
        x >>= 1;
        s -= 1uz;
    }//End while

    x = rev;
 }

 
 template<typename T>
 inline constexpr void set_leading_zeros(T& x)
 {

     reverse(x);

     x = (x - 1) | x;//Set trailing 0s to 1s
     
     reverse(x);
 }

编辑

因为有人问：我正在使用运行在 CPU 上的 MS-DOS，从早期的 X86 到安装在旧 CNC 机器上的 486DX。娱乐时间。：D

Answer 1

可以设置前导零而无需对它们进行计数，同时还可以避免反转整数。为了方便起见，我不会对通用整数类型 T 执行此操作，但可能可以对其进行调整，或者您可以使用模板专业化。

首先通过向下“扩展”位来计算所有不是前导零的位的掩码：

uint64_t m = x | (x >> 1);
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
m |= m >> 32;

然后设置该掩码未覆盖的所有位：

return x | ~m;

奖励：即使在设置了所有位时，此功能也会自动工作x = 0，x其中之一在计数前导零方法中可能会导致过大的移位量（哪一个取决于细节，但几乎总是其中之一很麻烦，因为有 65 种不同的情况，但只有 64 种有效的班次金额（如果我们谈论的是uint64_t）。

Answer 2

您可以使用计算前导零std::countl_zero并创建一个位掩码，将其与原始值按位或：

#include <bit>
#include <climits>
#include <type_traits>

template<class T>
requires std::is_unsigned_v<T>
T leading_ones(T v) {
    auto lz = std::countl_zero(v);
    return lz ? v | ~T{} << (CHAR_BIT * sizeof v - lz) : v;
}

如果你有一个std::uint16_t，比如

0b0001001101011111

那么~T{}是0b1111111111111111，CHAR_BIT * sizeof v是 16 ，countl_zero(v)是3。左移0b111111111111111116-3 步：

0b1110000000000000

与原来的按位或：

  0b0001001101011111
| 0b1110000000000000
--------------------
= 0b1111001101011111