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

编辑

因为有人询问：我正在使用在早期X86到486DX范围内安装在较旧的CNC机器上运行的MS-DOS。 真是有趣的时光。 :D

- dave_thenerd

---

有更快的方法来反转一个数字。 - Marc Glisse

无论您最终选择哪个解决方案，都可以使用它来清除前导1：clear_leading_ones(x) = ~set_leading_zeroes(~x)。 - harold

现代架构都有一条非常便宜的指令来获取前导零计数，而这个“rather expensive leading zero count”则意味着计算成本较高。 - phuclv

你谈到了“标准C++”，但是是哪个标准？C++11/14/17/20还是23...? 这也有点奇怪，因为我没有看到适用于MS-DOS的任何现代C++编译器。 - phuclv

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）。

- harold

---

@dave_thenerd：给定前导零计数，386和486上的shl/sar reg, cl或imm每个需要3个周期，但看起来bithack更快。即使您需要在32位CPU上进行扩展精度移位（例如shrd/shr）以进行uint64_t，shrd reg、reg、imm或cl也仅需要3个周期在386和486上。（实际上，在486上，shrd reg、reg、imm仅需要2个周期。在Pentium上，它是4个周期，而常规移位只需要1个周期，在U管道中可成对使用。） - Peter Cordes

你如何知道何时停止移动 m？对于给定的示例 0001 0011 0101 1111，在执行 m |= m >> 2 后，我得到了正确的掩码位，以便 return x | ~m 返回正确的值。 - puppydrum64

@puppydrum64，你可以检测m是否比某个2的幂次方少1（加1，然后使用著名的技巧之一来测试一个整数是否是2的幂次方），然后停止，但我认为这样做不值得。相对于几次移位和按位或运算非常便宜而言，这是相当大量的计算，然后是一个可能难以预测的分支。 - harold

我想我感到困惑是因为有五个连续的移位操作，而我字面上理解了它（即无论 x 和 m 的值如何都执行所有6行代码）。 - puppydrum64

@puppydrum64，实际上我打算这样使用它：无条件地执行所有6个步骤（或32位数字的5个步骤）。虽然可以提前退出，但在我看来似乎不值得。 - harold

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。将0b1111111111111111左移16-3个位置：

0b1110000000000000

与原始值进行按位或操作：

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

- Ted Lyngmo

---

谢谢，但是呃，我在问题中说过我知道前导零计数。我试图避免它，因为它非常慢。 - dave_thenerd

@dave_thenerd 你试过使用 countl_zero 吗？我预计它会非常快。 - Ted Lyngmo

你可能需要向编译器指定架构，popcnt 指令可能不会默认启用。（例如使用 gcc 的“-march=native”选项） - Marc Glisse

486确实具有位扫描指令，但作为一种微编码的逐位循环，需要花费与需要扫描的位数成比例的时间。 - harold

@TedLyngmo说：是的，现代编译器会使用bsr而不是位运算技巧（https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog），因为`bsr`在现代x86上速度很快（P6及以后的处理器延迟和吞吐量都只需要1个周期，在AMD上表现也不错；但令人惊讶的是，在P5 Pentium（https://www2.math.uni-wuppertal.de/~fpf/Uebungen/GdR-SS02/opcode_i.html）上，BSR甚至比BSF还要慢）。Harold的答案直接生成掩码（而不是计数），比位运算技巧更有效，位运算技巧有点类似于二分查找最高位位置。 - Peter Cordes

Answer 3

你的 reverse 非常慢！对于一个N位的整数，你需要N次迭代进行反转，每次至少需要6条指令，然后至少需要2条指令设置尾部位，最后再次迭代N次以再次反转该值。与此同时，即使是最简单的前导零计算只需要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的幂步骤进行操作，就像在哈罗德的答案中创建掩码的方法一样：

• 在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];
}

在 set_leading_zeros 中，只需要像上面那样调用 lut_ilog2_16。

比使用对数表更好的解决方案是使用掩码表，这样你可以直接获得掩码，而不用计算 1 << LogTable256[x]。

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

其他注意事项：

• 1uz 在 C++23 之前不是有效的后缀。
• 不要对那些适合放在单个整数中的小类型使用引用。这是不必要的，并且通常在未内联时会变慢。只需从函数中将结果赋回即可。

- phuclv

---

@TedLyngmo 这甚至更奇怪。我从未见过适用于 DOS 的 C++11 编译器，更别说 C++23 了。 - phuclv

Answer 4

工作正在进行中，这里的电力刚刚断掉；现在发布以保存我的工作。

陈旧的x86 CPU 在 C++20 中拥有非常缓慢的 std::countl_zero / GNU C __builtin_clz (386 bsr = Bit Scan Reverse 实际上找到了最高位的位置，如 31-clz，并且对于输入为 0 的情况很奇怪，所以您需要在其上进行分支。) 对于 Pentium Pro / Pentium II 之前的 CPU，生成掩码直接而不是计数是最好的选择，哈罗德的答案就是这样。

在386之前，通过大量移位可能最好使用部分寄存器trick，例如mov al，ah / mov ah，0而不是shr ax，8，因为286及更早版本没有用于常时移位的桶形移位器。但在C ++中，这是编译器需要解决的问题。由于32位整数只能在286或更早版本的一对16位寄存器中保留，因此移位16是免费的。

• 8086到286 - 没有可用的指令。

• 386: bsf/bsr: 10+3n个周期。最坏情况：10+3*31 = 103c

• 486: bsf (16或32位寄存器): 6-42个周期; bsr 7-104个周期 (16位寄存器少一个周期)。

• P5 Pentium: bsf: 6-42个周期(16位为6-34); bsr 7-71个周期。 (16位为7-39个周期)。不可成对使用。

• Intel P6及以后版本: bsr/bsr: 1个uop，1个周期吞吐量，3个周期延迟. (PPro / PII及更高版本)。

• AMD K7/K8/K10/Bulldozer/Zen: bsf/bsr对于现代CPU来说速度较慢。例如K10 3个周期吞吐量，4个周期延迟，分别为6/7 MOPS。

• Intel Haswell / AMD K10: 引入lzcnt(作为Intel的BMI1的一部分，或作为AMD自己的特性位，在tzcnt和BMI1的其他部分之前)。
  对于输入为0的情况，它们返回操作数大小，因此它们完全实现了C++20 std::countl_zero / countr_zero，不像bsr/bsf。(这些在输入=0时保留目标未更改。AMD文档中有记录，至少在当前CPU上，Intel实际上实现了这一点，但文档中将目标寄存器的内容定义为“未定义”。可能一些旧的Intel CPU有所不同，否则它只是令人恼火，因为它们没有记录这种行为，以便软件可以利用。)

  在AMD上，它们很快，单个uop用于lzcnt，tzcnt需要一个以上(可能是位反转以馈送lzcnt执行单元)，因此与bsf/bsr相比具有良好的优势。这就是为什么编译器通常在countr_zero / __builtin_ctz使用rep bsf，这样它就可以在支持它的CPU上作为tzcnt运行，但在旧的CPU上作为bsf运行。对于非零输入，它们产生相同的结果，不像bsr/lzcnt。

  在Intel上，与bsf/bsr相同的快速性能，甚至包括输出依赖性，直到Skylake修复为止;对于bsf/bsr，它是真正的依赖关系，但对于tzcnt/lzcnt和popcnt，它是错误的依赖关系。

---

使用位扫描构建块的快速算法

但是在P6（Pentium Pro）及更高版本中，对于寻找最高设置位的位扫描可能成为比log2（width）移位/或操作更快的策略的有用构建块，特别是对于64位机器上的uint64_t。（甚至在32位机器上的uint64_t上也是如此，其中每个移位都需要将位移到间隙中。）

来自https://www2.math.uni-wuppertal.de/~fpf/Uebungen/GdR-SS02/opcode_i.html的周期计数，其中包含8088到Pentium的指令时序。（但不包括指令获取瓶颈通常占据8086和尤其是8088性能的主导地位。）

bsr（最高位的索引）在现代x86上速度很快：P6及以后的处理器每周期吞吐量为1个，AMD上表现也不错。在更近期的x86上，BMI1 lzcnt 也是AMD上的1个周期，并且避免了输出依赖（在Skylake及更新版本中）。与bsr不同的是，它可以处理0作为输入（产生类型宽度，即操作数大小），而bsr会使目标寄存器保持不变。

我认为这个最好的版本（如果有BMI2）是受Ted Lyngmo答案启发的，但改为左/右移而不是生成掩码。ISO C++不能保证>>对于有符号整数类型是算术右移，但所有明智的编译器都选择将其作为其实现定义的行为。（例如，GNU C将其记录在文档中。） https://godbolt.org/z/hKohn8W8a 提供了这个想法，如果我们不需要处理x==0的话，那么确实很棒。

另外，如果我们考虑到可用的BMI2，可以使用BMI2 bzhi来提高效率。例如：x | ~ _bzhi_u32(-1, 32-lz);不幸的是，需要两个反转操作，即32-lzcnt和~。我们有BMI1的andn，但没有等效的orn。而且我们不能只使用neg，因为bzhi不会掩码计数；这就是整个问题所在，它对33个不同的输入具有独特的行为。明天可能会将这些发布为答案。

---

int set_leading_zeros(int x){
    int lz = __builtin_clz(x|1);                // clamp the lzcount to 31 at most
    int tmp = (x<<lz);                          // shift out leading zeros, leaving a 1 (or 0 if x==0)
    tmp |= 1ULL<<(CHAR_BIT * sizeof(tmp) - 1);  // set the MSB in case x==0
    return tmp>>lz;                             // sign-extend with an arithmetic right shift.
}

#include <immintrin.h>
uint32_t set_leading_zeros_bmi2(uint32_t x){
    int32_t lz = _lzcnt_u32(x);            // returns 0 to 32 
    uint32_t mask = _bzhi_u32(-1, lz);     // handles all 33 possible values, producing 0 for lz=32
    return x | ~mask;
}

在x86-64上，即使在Intel CPU上，结合BMI2的shlx/sarx可以实现单uop变量计数移位。

对于高效移位（BMI2或非英特尔处理器，如AMD），最好执行(x << lz) >> lz以进行符号扩展。但是如果lz是类型宽度，则需要生成掩码来处理。

不幸的是，在Sandybridge系列上，shl/sar reg，cl的成本为3个uops（因为x86遗留问题，如果计数恰好为零，则移位不会设置FLAGS），因此您需要BMI2 shlx/sarx才能比bsr ecx，dsr/mov tmp，-1/not ecx/shl tmp，cl/or dst，reg更好。

- Peter Cordes

---

待办事项，完成此任务并链接https://www.chessprogramming.org/BitScan#Bsf.2FBsr_x86-64_Timings - Peter Cordes

我刚刚偶然发现了这个“旧”的问题，并注意到你确实回来写了一个答案，正如你暗示的那样。 :-) 太好了！ - Ted Lyngmo