Is there an expression using modulo to do backwards wrap-around ("reverse overflow")?

ayane_m picture ayane_m · Feb 9, 2013 · Viewed 15.5k times · Source

For any whole number input W restricted by the range R = [x,y], the "overflow," for lack of a better term, of W over R is W % (y-x+1) + x. This causes it wrap back around if W exceeds y.

As an example of this principle, suppose we iterate over a calendar's months:

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

where both integers will be between 0 and 11, inclusive. Thus, the expression above "clamps" the integer to the range R = [0,11]. This approach of using an expression is simple, elegant, and advantageous as it omits branching.

Now, what if we want to do the same thing, but backwards? The following expression works:

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

but it's abstruse. How can it be beautified?


tl;dr - Can the expression ((x-1) % k + k) % k be simplified further?

Note: C++ tag specified because other languages handle negative operands for the modulo operator differently.

Answer

Fabian picture Fabian · Sep 28, 2016

Your expression should be ((x-1) + k) % k. This will properly wrap x=0 around to 11. In general, if you want to step back more than 1, you need to make sure that you add enough so that the first operand of the modulo operation is >= 0.

Here is an implementation in 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;}
}

This also allows to use months labeled from 0 to 11 or from 1 to 12, setting min_val and max_val accordingly.

Since this answer is so highly appreciated, here is an improved version without branching, which also handles the case where the initial value v is smaller than minval. I keep the other example because it is easier to understand:

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;
}

The only issue remaining is if minval is larger than maxval. Feel free to add an assertion if you need it.