使用模运算进行反向环绕(“逆溢出”)是否有表达式?

32

对于任何整数输入W,其范围限制为R=[x,y],则W超出R的"溢出",用缺乏更好术语的话来说,是W % (y-x+1) + x。如果W超过y,它会回到范围的开头。

举个例子说明这个原理,假设我们遍历一个日历的月份:

int this_month = 5;
int next_month = (this_month + 1) % 12;

两个整数的取值范围都在0到11之间,包括0和11。因此,上述表达式将整数“夹紧”到区间R=[0,11]中。使用表达式的方法简单、优雅且有利,因为它避免了分支

那么,如果我们想要做相反的事情呢?下面的表达式可以实现:

int last_month = ((this_month - 1) % 12 + 12) % 12;

但它很深奥。它如何能够变得更加美化呢?


tl;dr - 表达式((x-1) % k + k) % k还能进一步简化吗?

注意:指定C++标签是因为其他语言对于模运算符的负数操作数的处理方式不同。

6个回答

43

你的表达式应该是((x-1) + k) % k。这将正确地将 x=0 包装到 11。一般来说,如果你想要向后移动超过 1,你需要确保添加足够的数量,使得模运算的第一个操作数 >= 0。

以下是 C++ 的实现:

int wrapAround(int v, int delta, int minval, int maxval)
{
  const int mod = maxval + 1 - minval;
  if (delta >= 0) {return  (v + delta                - minval) % mod + minval;}
  else            {return ((v + delta) - delta * mod - minval) % mod + minval;}
}

这还允许使用从0到11或从1到12标记的月份,并根据需要设置min_valmax_val

由于此答案受到高度赞赏,因此这里提供了一个改进版本,不需要分支,还可以处理初始值v小于minval的情况。我保留了另一个示例,因为它更容易理解:

int wrapAround(int v, int delta, int minval, int maxval)
{
  const int mod = maxval + 1 - minval;
  v += delta - minval;
  v += (1 - v / mod) * mod;
  return v % mod + minval;
}

唯一需要关注的问题是如果minvalmaxval大。如果需要,可以随意添加断言。


9
解决方案是 ((x-1) + k) % k - CpILL
1
数字“-1”不能小于“-(k-1)” - Muhammad Umer
有人能解释一下为什么在(1-v/mod)*mod中要先除以mod然后再乘以mod吗?从数学上讲,这应该是没有意义的,但是去掉它会改变输出结果。 - BaconMan97
1
@BaconMan97 v/mod 是一个整数除法! - Fabian
@markzzz 确实输出了正确的9。请注意,min和max是包含的,因此min=0和max=10等于闭区间[0, 10],其中包括0、1、2、3、4、5、6、7、8、9、10这11个元素。向左移动2个元素是0 -> 10 -> 9。 - Fabian
显示剩余2条评论

7

k % k总是等于0。我不确定您试图做什么,但似乎您希望将上个月夹在0和11之间。

(this_month + 11) % 12

应该足够。

3
实际上,-1 % 12 == -1 - Mankarse
2
@Night5h4d3:在C++03中,如果任一操作数为负,则符号未指定。在C++11中,结果的符号与第一个操作数的符号相同(请参见我的答案)。 - Mankarse
在 Visual Studio 中(我正在使用的),-1%12 = -1。所以我被迫采用 ((x-1) % k + k) % k 的方式。 - ayane_m
非常感谢您提供这个。这正是我想要的。 - ayane_m
1
是的,如果你的增量/减量是已知或保证很小的话,这个方法是可行的。然而,只有在 x >= -12 的情况下,(this_month + x + 12)%12 才能按预期工作。在这个阈值以下,你仍然会遇到同样的问题。 - cmaster - reinstate monica
显示剩余3条评论

5
一般的解决方案是编写一个计算所需值的函数:
//Returns floor(a/n) (with the division done exactly).
//Let ÷ be mathematical division, and / be C++ division.
//We know
//    a÷b = a/b + f (f is the remainder, not all 
//                   divisions have exact Integral results)
//and
//    (a/b)*b + a%b == a (from the standard).
//Together, these imply (through algebraic manipulation):
//    sign(f) == sign(a%b)*sign(b)
//We want the remainder (f) to always be >=0 (by definition of flooredDivision),
//so when sign(f) < 0, we subtract 1 from a/n to make f > 0.
template<typename Integral>
Integral flooredDivision(Integral a, Integral n) {
    Integral q(a/n);
    if ((a%n < 0 && n > 0) || (a%n > 0 && n < 0)) --q;
    return q;
}

//flooredModulo: Modulo function for use in the construction
//looping topologies. The result will always be between 0 and the
//denominator, and will loop in a natural fashion (rather than swapping
//the looping direction over the zero point (as in C++11),
//or being unspecified (as in earlier C++)).
//Returns x such that:
//
//Real a = Real(numerator)
//Real n = Real(denominator)
//Real r = a - n*floor(n/d)
//x = Integral(r)
template<typename Integral>
Integral flooredModulo(Integral a, Integral n) {
    return a - n * flooredDivision(a, n);
}

4

非常简单,不要使用第一个模块运算符,它是多余的:

 int last_month = (this_month - 1 + 12) % 12;

这是一般情况。

在这种情况下,你可以写成11,但我仍然会写成-1 + 12,因为它更清楚地说明了你想要实现的目标。


3
请注意,普通模数会导致模式0...1112...2324...35等处重复,但不会在-11...-1上环绕。换句话说,它有两组行为。一组从-无穷大...-1开始,另一组从0...无穷大开始。

表达式((x-1) % k + k) % k可以修复-11...-1,但与普通模数在-23...-12上存在相同的问题。也就是说,虽然它修复了额外的12个数字,但它不能无限制地环绕。它仍然有一组从-无穷大...-12开始的行为,以及一组从-11...+无穷大开始的行为。

这意味着,如果您将该函数用于偏移量,可能会导致错误的代码。

如果要真正实现环绕式模数,则应以完全相同的方式处理整个范围-无穷大...无穷大

可能有更好的实现方法,但以下是易于理解的实现:

// n must be greater than 0
func wrapAroundMod(a: Int, n: Int) -> Int {
    var offsetTimes: Int = 0

    if a < 0 {
        offsetTimes = (-a / n) + 1
    }

    return (a + n * offsetTimes) % n
}

1
这应该是正确的答案!你能给我们一个没有分支的改进版本吗? - markzzz

2

不确定你是否遇到了和我一样的问题,我的问题本质上是想将所有数字限制在一个特定的范围内。比如说这个范围是0-6,那么使用%7就意味着任何大于6的数字都会重新回到0或更高的位置。但实际问题是小于零的数字并没有重新回到6。我有一个解决方案(其中X是数字范围的上限,0是最小值):

if(inputNumber <0)//If this is a negative number
{
(X-(inputNumber*-1))%X; 
}
else
{
inputNumber%X;
}

这里是一个简化版,用于获取0到maxVal之间的值(正模):(inputNumber % maxVal + maxVal) % maxVal - XenialDan

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接