8

对于给定的数字和x，我想在 C 中计算。看看这个例子：ynx-y mod n

int substract_modulu(int x, int y, int n)
{
    return (x-y) % n;
}

只要x>y，我们都很好。然而，在另一种情况下，模运算是undefined。

你可以想到x,y,n>0。我希望结果是正数，所以如果(x-y)<0, then((x-y)-substract_modulu(x,y,n))/ n应该是一个整数。

你知道的最快的算法是什么？有没有一个可以避免任何调用ifand operator?？

4

7 回答 7

7

正如许多人指出的那样，在当前的 C 和 C++ 标准中，x % n不再为x和的任何值定义实现n。x / n在未定义 [1]的情况下，它是未定义的行为。此外，x - y在整数溢出的情况下是未定义的行为，如果 和 的符号可能不同，这是可能x的y。

因此，通用解决方案的主要问题是避免整数溢出，无论是在除法还是减法中。如果我们知道xandy是非负的并且n是正的，那么溢出和被零除是不可能的，我们可以自信地说这(x - y) % n是定义的。不幸的是，x - y可能是负数，在这种情况下，%运算符的结果也是如此。

n如果我们知道结果是肯定的，就很容易纠正结果是否定的；我们所要做的就是无条件地添加n并执行另一个modulo操作。这不太可能是最好的解决方案，除非你有一台除法比分支快的计算机。

如果有条件加载指令可用（这几天很常见），那么编译器可能会很好地处理以下代码，这些代码是可移植且定义明确的，受以下约束x,y ≥ 0 ∧ n > 0：

((x - y) % n) + ((x >= y) ? 0 : n)

例如，gcc 为我的核心 I5 生成此代码（尽管它的通用性足以在任何非古生代英特尔芯片上工作）：

    idivq   %rcx
    cmpq    %rsi, %rdi
    movl    $0, %eax
    cmovge  %rax, %rcx
    leaq    (%rdx,%rcx), %rax

这是愉快的无分支。（条件移动通常比分支快得多。）

另一种方法是（除了sign需要编写函数）：

((x - y) % n) + (sign(x - y) & (unsigned long)n)

如果sign参数为负数，则全为 1，否则为 0。符号的一种可能实现（改编自bithacks）是

unsigned long sign(unsigned long x) {
  return x >> (sizeof(long) * CHAR_BIT - 1);
}

这是可移植的（定义了将负整数值转换为无符号），但在缺乏高速移位的架构上可能会很慢。它不太可能比以前的解决方案更快，但是 YMMV。蒂亚斯。

对于可能整数溢出的一般情况，这些都不会产生正确的结果。处理整数溢出非常困难。（一个特别烦人的情况是n == -1，尽管您可以对其进行测试并返回 0 而无需使用%。）此外，您需要确定您对负模结果的偏好n。我个人更喜欢定义x%n为 0 或具有相同符号的定义n- 否则你为什么要使用负除数 - 但应用程序不同。

n如果不是-1并且n + n不会溢出，Tom Tanner 提出的三模解决方案将有效。n == -1如果是xor将失败，如果yis ，使用而不是的INT_MIN简单修复将失败。绝对值大的情况可以用比较代替，但是有很多极端情况，而且由于标准不需要2的补码算法，所以很难预测什么是极端情况。 [2]。abs(n)nnINT_MINn

最后一点，一些诱人的解决方案不起作用。你不能只取 的绝对值(x - y)：

(-z) % n == -(z % n) == n - (z % n) ≠ z % n（除非z % n碰巧是n / 2）

而且，出于同样的原因，您不能只取模结果的绝对值。

此外，您不能只(x - y)转换为无符号：

(unsigned)z == z + 2k (for some k) if z < 0
(z + 2k) % n == (z % n) + (2k % n) ≠ z % n除非(2k % n) == 0

[1]x/n并且x%n如果n==0. 但是x%n如果是“不可表示”（即整数溢出）也是未定义x/n的，这将发生在二进制补码机器（即您关心的所有机器）上，如果x是最负的可表示数并且n == -1. 很清楚为什么x/n在这种情况下应该是 undefined ，但在 的情况下稍微少一些x%n，因为该值是（数学上）0。

[2] 大多数抱怨预测浮点运算结果困难的人并没有花太多时间尝试编写真正可移植的整数运算代码:)

于 2012-12-25T17:28:37.280 回答
4

如果您想避免未定义的行为，如果没有 if，以下将起作用

return (x % n - y % n + n) % n;

效率取决于模运算的实现，但我怀疑涉及的算法if会更快。

或者，您可以将xandy视为未签名。在这种情况下，不涉及负数，也没有未定义的行为。

于 2012-12-25T10:01:08.683 回答
2

在 C++11 中，未定义的行为被移除。根据您想要的确切行为，您可以坚持

return (x-y) % n;

有关完整解释，请阅读此答案：

https://stackoverflow.com/a/13100805/1149664

对于 n==0 或者如果 xy 不能存储在您正在使用的类型中，您仍然会得到未定义的行为。

于 2012-12-25T11:05:40.053 回答
1

分支是否重要在某种程度上取决于 CPU。根据文档abs（在MSDN上）具有内在行为，它可能根本不是瓶颈。这个你必须测试。

如果您不想无条件地计算事物，那么可以从Bit Twiddling Hacks 网站改编一些不错的方法。

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

但是，如果没有有关硬件目标和测试的更多信息，我不知道这是否会对您的情况有所帮助。

只是出于好奇，我不得不自己对此进行测试，当您查看编译器生成的程序集时，我们可以看到使用abs.

unsigned r = abs(i);
====
00381006  cdq              
00381007  xor         eax,edx 
00381009  sub         eax,edx

以下只是上述示例的另一种形式，根据 Bit Twiddling Site 没有专利（而 Visual C++ 2008 编译器使用的版本是）。

在我的回答中，我一直在使用 MSDN 和 Visual C++，但我认为任何理智的编译器都有类似的行为。

于 2012-12-25T10:08:49.087 回答
1

假设0 <= x < n和0 <= y < n，怎么样(x + n - y) % n？那么 x + n 肯定会大于 y，减去 y 总是会得到一个正整数，最后的 mod n 必要时会减少结果。

于 2012-12-25T17:36:39.963 回答
0

我猜这里的情况并非如此，但我想提一下，如果你取模的值是 2 的幂，那么使用“AND”方法会快得多（我m 将忽略 xy，只显示它对单个 x 的工作原理，因为 xy 不是这里等式的一部分）：

int modpow2(int x, int n)
{
    return x & (n-1);
}

如果您想确保您的代码不会做任何愚蠢的事情，您可以添加ASSERT(!(n & n-1));- 这会检查是否只设置了一个位n（因此，n是 2 的幂）。

于 2012-12-25T11:02:30.383 回答
0

这是我在竞争性编程中使用的 CPP 代码：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll          long long
#define  mod         1000000007

ll subtraction_modulo(ll x, ll y ){
        return ( ( (x - y) %  mod ) +  mod ) %  mod;
    }

这里，

ll -> long long int

mod -> 要使用的全局定义的 mod 值。

于 2018-07-20T07:39:11.067 回答