快速取整定点数

Question

假设我把我的整数看作带有4位小数的数。现在，0是零，16是一，32是二，以此类推。在四舍五入时，范围在[-7，7]内的数字变成0，[8，23]内的数字变成16。

我的代码如下：

std::int64_t my_round(std::int64_t n) {
    auto q = n / 16;
    auto r = n % 16;
    if (r >= 0) {
        if (r >= 8) {
            ++q;
        }
    } else {
        if (r <= -8) {
            --q;
        }
    }
    return q * 16;
}

这个简单的任务需要很多代码，我想知道是否有更快的方法来完成它。我只需要支持64位带符号整数。

编辑： 有人评论建议添加15并掩码低位，但这并不起作用。但通过一些试错，我想出了以下解决方案。

std::int64_t my_round2(std::int64_t n) {
    if (n >= 0) {
        n += 8;
    }
    else {
        n += 7;
    }
  return n & (~15ll);
}

我不知道，但是my_round2似乎和my_round得到了相同的结果，而且速度快了20倍。如果有办法去掉分支，那就更好了。

- W.H

---

当您启用优化编译时，您可能需要检查生成的汇编代码，因为您正在使用2的幂8和16，编译器很可能能够将整数运算替换为位运算，因此生成的可执行文件已经非常高效。如果是这样，那么重写函数使其更短可能不会为您带来任何运行时效率的提升，但它会使函数更难以理解。 - Jeremy Friesner

在my_round2()中，n += 8; 可能导致溢出。Wei Hsieh，您想如何处理溢出？ - chux - Reinstate Monica

@WeiHsieh my_round2(-15) 应该返回什么？ - chux - Reinstate Monica

@WeiHsieh 这里采用的舍入模式是将中间值向远离零的方向舍入。这与常见的FP“四舍五入，遇到平局则向偶数舍入”的方式不同。我猜你更注重速度而非“减少偏差”（reduce bias）的实践，但采用不同的舍入方式可能会提高你算法的质量。 - chux - Reinstate Monica

@WeiHsieh “我在想是否有更快的方法来做这件事。” 存在早期优化的风险。使用你的 my_round2() 后续步骤会依赖于处理器，适用于 64 位机器的方法在 16 位嵌入式处理器上可能表现极差。也许可以标记感兴趣的处理器系列？ - chux - Reinstate Monica

Answer 1

随着

return (n + 8 + (n>>63)) & (~15ll);

可以从my_round2()中删减分支，同时确保在0处原始对称性不变。想法是有符号整数 >> (sizeof(有符号整数) * 8 - 1) 对于负数的结果为-1，对于正数的结果为0。

Clang能够为原始的my_round2()生成无分支代码，但仍比此处提出的程序长一条指令。在arm64上节省的更多。

- Aki Suihkonen

---

不错。另一种选择是用“-(n<0)”替换“+(n>>63)”，这对我来说更清晰，但可能需要更多依赖于编译器优化以生成快速代码。 - nielsen

“signed type >> (sizeof(signed type) * 8 - 1) is -1 for negative values” 是_实现定义的_。这也是C规范中IDB的一个例子：“实现定义行为的一个例子是当有符号整数向右移位时高位比特的传播。” -(n<0) (@nielsen) 是一个很好的替代方案。 - chux - Reinstate Monica

是的，在二进制补码和所有样板文件中，当然还有一些具有9位字符的系统。但 std::int64_t 据我所知保证是二进制补码。（https://dev59.com/wGYr5IYBdhLWcg3whKmt） - Aki Suihkonen

int64_t必须是二进制补码且未填充，但代码仍具有实现定义的行为。是的，通常情况下IDB会按照期望的方式运行，但这并非必需 - 即使编码是2的补码。问题在于，明天的编译器可能会以今天未曾预料的方式利用规范。许多过去编写的遵循常见做法的代码由于类似的原因而在今天失败。由你决定。 - chux - Reinstate Monica

Answer 2

如何像这样呢？

std::int64_t my_round2(std::int64_t n) {
    int sign = n >= 0 ? 1 : -1;
    n = sign > 0 ? n: -n;
    int64_t n1 = (n + 8) >>4;
    n1<<= 4;
    return n1 * sign;
}

这个仍然存在溢出问题。

- Zoso

---

@chux-ReinstateMonica：奇怪是我选择的恰当形容词。我不记得为什么会突然使用 size_t。我已将其更改为 int64_t。 - Zoso

注意：使用int64_t n1，n1<<= 4; 可能导致_未定义行为_：使用 uint64_t n1 ，代码不会有 UB，但会产生各种 _实现定义的行为_。 - chux - Reinstate Monica

Answer 3

只要您的整数表示是二进制补码（在C11标准中几乎是必需的），只需添加8并屏蔽低位即可：

int64_t my_round2(int64_t n) {
    return (n + 8) & ~UINT64_C(15);
}

- Chris Dodd

---

如果n为-8，则结果为0，但似乎OP希望在这种情况下为-1。 - nielsen