29

範囲R = [ x , y ]によって制限された任意の整数入力Wについて、 Rに対するWの "オーバーフロー" (適切な項がないため)は です。これにより、 Wがyを超えると折り返しが発生します。W % (y-x+1) + x

この原則の例として、カレンダーの月を反復するとします。

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

ここで、両方の整数は 0 から 11 の間になります。したがって、上記の式は整数を範囲R = [0,11] に「クランプ」します。式を使用するこのアプローチは、シンプルで洗練されており、分岐を省略できるため有利です。

では、逆に同じことをしたい場合はどうすればよいでしょうか? 次の式が機能します。

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

しかし難解です。どうしたら美化できる？

tl;dr - 式((x-1) % k + k) % kをさらに簡略化できますか?

注: C++ タグが指定されているのは、他の言語では剰余演算子の負のオペランドの処理が異なるためです。

4

6 に答える 6

37

あなたの表現は((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_valますmax_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です。必要に応じてアサーションを自由に追加してください。

于 2016-09-28T06:51:55.527 に答える
7

k % kは常に 0 になります。あなたが何をしようとしているのか 100% はわかりませんが、先月を 0 から 11 の間にクランプしたいようです。

(this_month + 11) % 12

十分なはずです。

于 2013-02-09T06:09:03.087 に答える
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);
}
于 2013-02-09T06:16:02.480 に答える