Clean, efficient algorithm for wrapping integers in C++


Question

/**
  * Returns a number between kLowerBound and kUpperBound
  * e.g.: Wrap(-1, 0, 4); // Returns 4
  * e.g.: Wrap(5, 0, 4); // Returns 0      
  */
int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
    // Suggest an implementation?
}
1
27
4/1/2009 9:18:35 PM

Accepted Answer

The sign of a % b is only defined if a and b are both non-negative.

int Wrap(int kX, int const kLowerBound, int const kUpperBound)
{
    int range_size = kUpperBound - kLowerBound + 1;

    if (kX < kLowerBound)
        kX += range_size * ((kLowerBound - kX) / range_size + 1);

    return kLowerBound + (kX - kLowerBound) % range_size;
}
30
4/7/2009 6:17:14 AM

The following should work independently of the implementation of the mod operator:

int range = kUpperBound - kLowerBound + 1;
kx = ((kx-kLowerBound) % range);
if (kx<0)
  return kUpperBound + 1 + kx;
else
  return kLowerBound + kx;

An advantage over other solutions is, that it uses only a single % (i.e. division), which makes it pretty efficient.

Note (Off Topic):

It's a good example, why sometimes it is wise to define intervals with the upper bound being being the first element not in the range (such as for STL iterators...). In this case, both "+1" would vanish.


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon