c++ 有没有一个表达式使用模来做向后回绕(“反向溢出”)?

ckocjqey  于 2023-04-08  发布在  其他
关注(0)|答案(6)|浏览(93)

对于任何整数输入 W,受范围 R = [xy]的限制,WR 上的“溢出”(由于缺乏更好的术语)是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++标记是因为其他语言对取模运算符的负操作数的处理方式不同。*
xfyts7mz

xfyts7mz1#

你的表达式应该是((x-1) + k) % k。这将正确地将x=0 Package 到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;
}

剩下的唯一问题是minval是否大于maxval。如果需要,请随时添加Assert。

yc0p9oo0

yc0p9oo02#

  • k % k* 将永远是0。我不是100%确定你想做什么,但似乎你希望最后一个月被夹在0和11之间。
(this_month + 11) % 12

应该够了

92dk7w1h

92dk7w1h3#

一般的解决方案是写一个函数来计算你想要的值:

//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);
}
sczxawaw

sczxawaw4#

Easy Peasy,不要使用第一个模块运算符,它是多余的:

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

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

ykejflvf

ykejflvf5#

注意,normal mod会导致模式0...1112...2324...35等处重复,但不会在-11...-1上换行。换句话说,它有两组行为。一组来自-infinity...-1,另一组来自0...infinity
表达式((x-1) % k + k) % k修复了-11...-1,但与-23...-12的普通mod有相同的问题。即,虽然它修复了12个额外的数字,但它不会无限地环绕。它仍然具有-infinity...-12的一组行为,以及-11...+infinity的不同行为。
这意味着,如果您使用函数进行偏移,可能会导致错误代码。
如果你想要一个真正的环绕mod,它应该以完全相同的方式处理整个范围,-infinity...infinity
可能有更好的方法来实现这一点,但这里有一个易于理解的实现:

// 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
}
pdtvr36n

pdtvr36n6#

不知道你是否和我有同样的问题,但我的问题本质上是我想把所有的数字限制在一个特定的范围内,假设这个范围是0-6,所以使用%7意味着任何大于6的数字都将返回到0或更高。实际问题是小于0的数字不会返回到6。我有一个解决方案(其中X是数字范围的上限,0是最小值):

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

相关问题