负数的模运算

Question

可能是重复问题：
负数取模问题

我想知道是否有更好的算法来实现我的需求：

wrapIndex(-6, 3) = 0
wrapIndex(-5, 3) = 1
wrapIndex(-4, 3) = 2
wrapIndex(-3, 3) = 0
wrapIndex(-2, 3) = 1
wrapIndex(-1, 3) = 2
wrapIndex(0, 3) = 0
wrapIndex(1, 3) = 1
wrapIndex(2, 3) = 2
wrapIndex(3, 3) = 0
wrapIndex(4, 3) = 1
wrapIndex(5, 3) = 2

我得到了以下代码：

function wrapIndex(i, i_max) {
        if(i > -1)
            return i%i_max;
var x = i_max + i%i_max;
        if(x == i_max)
            return 0;
return x;
    }

是否有更好的方法来做这个?

- fresskoma

---

这是 Mod of negative number is melting my brain! 的副本，以及此网站上至少十几个类似的问题的副本。 :-) - ShreevatsaR

嗯，我搜索了负数的模数，但并没有找到什么... 对不起又发了一个重复的。 - fresskoma

int mod(int k, int n) { return ((k %= n) < 0) ? k+n : k; } - Evgeni Sergeev

在Python中，如果n是正数，那么(k % n)始终为正数。 - Evgeni Sergeev

Answer 1

这个解决方案是无分支的，但是运行了两次 % 。

function wrapIndex(i, i_max) {
   return ((i % i_max) + i_max) % i_max;
}

需要指出的是，C＃/Java中%运算符的行为是被假定的，即结果具有与被除数相同的符号。一些语言定义余数计算采用除数的符号（例如Clojure中的mod）。一些语言具有两种变体（Common Lisp、Haskell等中的mod/rem对）。Algol-68有一个%x，它总是返回非负数。在C++11之前，C++将其留给了实现，现在根据被除数的符号几乎完全规定了余数的符号。

另请参阅

• Wikipedia / Modulo operation

- polygenelubricants

---

+1 因为它实际上有效。;-) - Paul Sasik

带有分支的版本会返回i_max，以便负数倍数的i_max。 - Maciej Hehl

@Maciej：你说得对；完全去掉它（因为我也不是它的粉丝；只是想要“完整”）。 - polygenelubricants

Answer 2

两个 % 操作的解决方案可行，但在大多数语言和硬件上，以下方法会更快（然而有一些例外）：

int wrapIndex(int i, int i_max) {
    i = i%i_max;
    return i<0 ? i+i_max : i;
}

- Stephen Canon

---

等等，分支比 2x % 更快？难以置信。 - Youda008

Answer 3

更好的感觉是一个品味问题，但是怎么样呢？

var x = (i_max + i % i_max) % i_max;

- Maciej Hehl

---

我真的感到不舒服给这个点赞，因为我不知道Java或者其他语言的确切操作优先级规则，但是我相信你知道自己在做什么（谢谢纠正，我看到至少有3个人包括我在这里都犯了这个错误）。 - polygenelubricants

@polygenelubricants：在现代语言中，％的优先级高于+。 - Stephen Canon

Answer 4

你可以这样做：

function wrapIndex(i, i_max) {
    if (i < 0) i = (i % i_max) + i_max;
    return i % i_max;
}

- Gumbo

---

以前的版本是正确的 :) 如果 (i % i_max) == 0，则 (i % i_max) + i_max 可能等于 i_max - Maciej Hehl

@Maciej Hehl：该死，你是对的。 - Gumbo

Answer 5

许多用户提供了很好的答案，但要注意负数，因为不同的语言可能会有不同的行为。例如，这个C代码片段会输出“-1”。

int main ()
{
    printf("%d\n", (-4) % 3);
}

在Python中，我们有不同的输出值。

Python 2.6.4 (r264:75706, Dec  7 2009, 18:43:55) 
[GCC 4.4.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> (-4) % 3
2

编辑：实际上我不认为你会有负数索引！但是了解这一点很好。

- Dacav