在任意大小的整数C中设置前导零比特

Question

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

例如。

0001 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);
 }

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

Answer 1

你的反面非常慢！使用 N 位 int 时，您需要 N 次迭代来反转，每次至少 6 条指令，然后至少 2 条指令来设置尾随位，最后 N 次迭代以再次反转该值。OTOH即使是最简单的前导零计数也只需要N次迭代，然后直接设置前导位：

template<typename T>
inline constexpr T trivial_ilog2(T x) // Slow, don't use this
{
    if (x == 0) return 0;

    size_t c{};
    while(x)
    {
        x >>= 1;
        c += 1u;
    }

    return c;
}

template<typename T>
inline constexpr T set_leading_zeros(T x)
{
    if (std::make_unsigned_t(x) >> (sizeof(T) * CHAR_BIT - 1)) // top bit is set
        return x;
    return x | (-T(1) << trivial_ilog2(x));
}

x = set_leading_zeros(x);

还有许多其他方法可以更快地计算前导零/获取整数对数。其中一种方法涉及按照2的幂步骤进行操作，例如如何在harold的答案中创建面具：

• 在C中查找整数中的最高设置位（msb）的最快/最有效的方法是什么？
• 查找C中的最高位
• 如何高效计数小于或等于给定数字的2的最高幂？
• http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup

但是由于你是针对一个特定的目标而不是跨平台做一些事情，并且想要压缩每一点性能，所以几乎没有理由使用纯标准特性，因为这些用例通常需要特定于平台的代码。如果内部函数可用，你应该使用它，例如在现代C中，有std::countl_zero，但是每个编译器已经有内部函数来做这件事，它将映射到该平台的最佳指令序列，例如_BitScanReverse或__builtin_clz

如果内在函数不可用，如果性能仍然不够，则尝试查找表。例如，这是一个具有256元素日志表的解决方案

static const char LogTable256[256] = 
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

uint16_t lut_ilog2_16(uint16_t x)
{
    uint8_t h = x >> 8;
    if (h) return LogTable256[h] + 8;
    else return LogTable256[x & 0xFF];
}

在< code>set_leading_zeros中，只需像上面那样调用< code>lut_ilog2_16

比日志表更好的解决方案是掩码表，这样您可以直接获得掩码，而不用计算< code>1

static const char MaskTable256[256] =
{
    0xFF, 0xFE, 0xFC...
}

其他一些注意事项:

null

Answer 2

您可以使用< code>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;
}

如果您有标准：：uint16_t，喜欢

0b0001001101011111

然后~T{}是0b1111111111111111，CHAR_BIT*sizeof v是16，countl_zero（v）是3。左移0b1111111111111116-3步骤：

0b1110000000000000

按位或与原始：

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

Answer 3

可以设置前导零而不对它们进行计数，同时还可以避免反转整数。为了方便起见，我不会对通用整数类型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）。