80

通常在我的内部循环中，我需要以“环绕”方式索引一个数组，因此（例如）如果数组大小为 100 并且我的代码要求元素 -2，则应该给它元素 98。在许多高级语言（如 Python）可以简单地使用 来做到这一点my_array[index % array_size]，但由于某种原因，C 的整数运算（通常）向零舍入而不是始终向下舍入，因此当给定负的第一个参数时，它的模运算符返回负结果。

通常我知道index不会少于-array_size，在这些情况下我只是这样做my_array[(index + array_size) % array_size]。但是，有时这无法保证，对于这些情况，我想知道实现始终为正的模函数的最快方法。有几种“聪明”的方法可以在没有分支的情况下做到这一点，例如

inline int positive_modulo(int i, int n) {
    return (n + (i % n)) % n;
}

或者

inline int positive_modulo(int i, int n) {
    return (i % n) + (n * (i < 0));
}

当然，我可以分析这些以找出在我的系统上哪个是最快的，但我不禁担心我可能错过了一个更好的，或者我的机器上的快速可能在不同的机器上很慢。

那么有没有一种标准的方法来做到这一点，或者我错过的一些聪明的技巧可能是最快的方法？

另外，我知道这可能是一厢情愿的想法，但如果有一种方法可以自动矢量化，那就太棒了。

4

9 回答 9

86

The standard way I learned is

inline int positive_modulo(int i, int n) {
    return (i % n + n) % n;
}

This function is essentially your first variant without the abs (which, in fact, makes it return the wrong result). I wouldn't be surprised if an optimizing compiler could recognize this pattern and compile it to machine code that computes an "unsigned modulo".

Edit:

Moving on to your second variant: First of all, it contains a bug, too -- the n < 0 should be i < 0.

This variant may not look as if it branches, but on a lot of architectures, the i < 0 will compile into a conditional jump. In any case, it will be at least as fast to replace (n * (i < 0)) with i < 0? n: 0, which avoids the multiplication; in addition, it's "cleaner" because it avoids reinterpreting the bool as an int.

As to which of these two variants is faster, that probably depends on the compiler and processor architecture -- time the two variants and see. I don't think there's a faster way than either of these two variants, though.

于 2013-02-21T08:13:09.587 回答
30

模二的幂，以下工作（假设二进制补码表示）：

return i & (n-1);
于 2013-02-21T08:02:31.793 回答
24

大多数时候，编译器非常擅长优化你的代码，所以通常最好让你的代码保持可读性（让编译器和其他开发人员都知道你在做什么）。

由于您的数组大小始终为正，我建议您将商定义为unsigned. 编译器会将小的 if/else 块优化为没有分支的条件指令：

unsigned modulo( int value, unsigned m) {
    int mod = value % (int)m;
    if (mod < 0) {
        mod += m;
    }
    return mod;
}

这将创建一个没有分支的非常小的函数：

modulo(int, unsigned int):
        mov     eax, edi
        cdq
        idiv    esi
        add     esi, edx
        mov     eax, edx
        test    edx, edx
        cmovs   eax, esi
        ret

例如modulo(-5, 7)返回2。

不幸的是，由于商不知道，它们必须执行整数除法，这与其他整数运算相比有点慢。如果您知道数组的大小是 2 的幂，我建议将这些函数定义保留在头文件中，以便编译器可以将它们优化为更有效的函数。这是功能unsigned modulo256(int v) { return modulo(v,256); }：

modulo256(int):                          # @modulo256(int)
        mov     edx, edi
        sar     edx, 31
        shr     edx, 24
        lea     eax, [rdi+rdx]
        movzx   eax, al
        sub     eax, edx
        lea     edx, [rax+256]
        test    eax, eax
        cmovs   eax, edx
        ret

见组装：https ://gcc.godbolt.org/z/DG7jMw

查看与投票最多的答案的比较：http: //quick-bench.com/oJbVwLr9G5HJb0oRaYpQOCec4E4

基准比较

编辑：原来 Clang 能够在没有任何条件移动指令的情况下生成一个函数（这比常规算术运算成本更高）。这种差异在一般情况下完全可以忽略不计，因为积分除法需要大约 70% 的总时间。

基本上，Clangvalue向右移动以将其符号位扩展到整个宽度m（即0xffffffff当为负时，0否则为），用于屏蔽mod + m.

unsigned modulo (int value, unsigned m) {
    int mod = value % (int)m;
    m &= mod >> std::numeric_limits<int>::digits;
    return mod + m;
}
于 2019-09-26T14:19:30.197 回答
9

使用二进制补码符号位传播获取可选加数的老式方法：

int positive_mod(int i, int m)
{
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1;
    int r = i%m;
    return r+ (r>>shift & m);
}
于 2013-02-22T04:46:52.687 回答
7

在 C/C++ 中获得正模的最快方法

下面快？- 可能不如其他人快，但对于所有1 a,b来说都是简单且功能正确的- 与其他人不同。

int modulo_Euclidean(int a, int b) {
  int m = a % b;
  if (m < 0) {
    // m += (b < 0) ? -b : b; // avoid this form: -b is UB when b == INT_MIN
    m = (b < 0) ? m - b : m + b;
  }
  return m;
}

其他各种答案都有mod(a,b)弱点，尤其是在b < 0.

见欧几里得除法有关的想法b < 0

inline int positive_modulo(int i, int n) {
    return (i % n + n) % n;
}

溢出时失败i % n + n（想想大i, n） - 未定义的行为。

return i & (n-1);

依靠n为二的幂。（公平的答案确实提到了这一点。）

int positive_mod(int i, int n)
{
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1;
    int m = i%n;
    return m+ (m>>shift & n);
}

时常失败n < 0。e, g,positive_mod(-2,-3) --> -5

int32_t positive_modulo(int32_t number, int32_t modulo) {
    return (number + ((int64_t)modulo << 32)) % modulo;
}

强制使用 2 个整数宽度。（公平地说，答案确实提到了这一点。）
失败modulo < 0。 positive_modulo(2, -3)--> -1。

inline int positive_modulo(int i, int n) {
    int tmp = i % n;
    return tmp ? i >= 0 ? tmp : tmp + n : 0;
}

时常失败n < 0。e, g,positive_modulo(-2,-3) --> -5

1例外情况：在 C 中，a%b未定义如中或a/b中的溢出时。a/0INT_MIN/-1

于 2019-08-18T12:14:43.353 回答
3

如果您想避免所有条件路径（包括上面生成的条件移动，（例如，如果您需要此代码进行矢量化，或在恒定时间内运行），您可以使用符号位作为掩码：

unsigned modulo(int value, unsigned m) {
  int shift_width = sizeof(int) * 8 - 1;
  int tweak = (value >> shift_width);
  int mod = ((value - tweak) % (int) m) + tweak;
  mod += (tweak & m);
  return mod;
}

这是quickbench 结果您可以看到在 gcc 上它在通用情况下更好。对于 clang，它在通用情况下的速度相同，因为 clang 在通用情况下生成无分支代码。无论如何，该技术很有用，因为不能总是依赖编译器来产生特定的优化，并且您可能必须手动滚动它以获得矢量代码。

于 2020-04-27T21:53:04.813 回答
3

如果您有能力升级到更大的类型（并对更大的类型进行模运算），则此代码执行单个模运算，并且如果：

int32_t positive_modulo(int32_t number, int32_t modulo) {
    return (number + ((int64_t)modulo << 32)) % modulo;
}
于 2018-10-09T16:49:25.247 回答
2

您也可以这样做array[(i+array_size*N) % array_size]，其中 N 是足够大的整数以保证正参数，但足够小以不会溢出。

当 array_size 是常数时，有一些技术可以计算模数而不用除法。除了两种方法的幂，可以计算位组的加权和乘以 2^i % n，其中 i 是每组中的最低有效位：

例如32位整数0xaabbccdd % 100 = dd + cc*[2]56 + bb*[655]36 + aa*[167772]16，最大范围为(1+56+36+16)*255 = 27795 . 通过重复应用和不同的细分，可以将操作减少到很少的条件减法。

常见的做法还包括用 2^32 / n 的倒数近似除法，这通常可以处理相当大范围的参数。

 i - ((i * 655)>>16)*100; // (gives 100*n % 100 == 100 requiring adjusting...)
于 2013-02-21T12:09:12.667 回答
1

你的第二个例子比第一个好。乘法是一个比 if/else 操作更复杂的操作，所以使用这个：

inline int positive_modulo(int i, int n) {
    int tmp = i % n;
    return tmp ? i >= 0 ? tmp : tmp + n : 0;
}
于 2015-09-16T15:10:12.190 回答