Clean, efficient algorithm for wrapping integers i

问题:

/**
  * 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:

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

回答2:

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.

回答3:

Fastest solution, least flexible: Take advantage of native datatypes that will do wrapping in the hardware.

The absolute fastest method for wrapping integers would be to make sure your data is scaled to int8/int16/int32 or whatever native datatype. Then when you need your data to wrap the native data type will be done in hardware! Very painless and orders of magnitude faster than any software wrapping implementation seen here.

As an example case study:

I have found this to be very useful when I need a fast implementation of sin/cos implemented using a look-up-table for a sin/cos implementation. Basically you make scale your data such that INT16_MAX is pi and INT16_MIN is -pi. Then have you are set to go.

As a side note, scaling your data will add some up front finite computation cost that usually looks something like:

int fixedPoint = (int)( floatingPoint * SCALING_FACTOR + 0.5 )

Feel free to exchange int for something else you want like int8_t / int16_t / int32_t.

---

Next fastest solution, more flexible: The mod operation is slow instead if possible try to use bit masks!

Most of the solutions I skimmed are functionally correct... but they are dependent on the mod operation.

The mod operation is very slow because it is essentially doing a hardware division. The laymans explanation of why mod and division are slow is to equate the division operation to some pseudo-code for(quotient = 0;inputNum> 0;inputNum -= divisor) { quotient++; } ( def of quotient and divisor ). As you can see, the hardware division can be fast if it is a low number relative to the divisor... but division can also be horribly slow if it is much greater than the divisor.

If you can scale your data to a power of two then you can use a bit mask which will execute in one cycle ( on 99% of all platforms ) and your speed improvement will be approximately one order of magnitude ( at the very least 2 or 3 times faster ).

C code to implement wrapping:

#define BIT_MASK (0xFFFF)
int wrappedAddition(int a, int b) {
    return ( a + b ) & BIT_MASK;
}
int wrappedSubtraction(int a, int b) {
    return ( a - b ) & BIT_MASK;
}

Feel free to make the #define something that is run time. And feel free to adjust the bit mask to be whatever power of two that you need. Like 0xFFFFFFFF or power of two you decide on implementing.

---

p.s. I strongly suggest reading about fixed point processing when messing with wrapping/overflow conditions. I suggest reading:

Fixed-Point Arithmetic: An Introduction by Randy Yates August 23, 2007

回答4:

Please do not overlook this post. :)

Is this any good?

int Wrap(N,L,H){
  H=H-L+1; return (N-L+(N<L)*H)%H+L;
}

This works for negative inputs, and all arguments can be negative so long as L is less than H.

Background... (Note that H here is the reused variable, set to original H-L+1).

I had been using (N-L)%H+L when incrementing, but unlike in Lua, which I used before starting to learn C a few months back, this would NOT work if I used inputs below the lower bound, never mind negative inputs. (Lua is built in C, but I don't know what it's doing, and it likely wouldn't be fast...)

I decided to add +(N<L)*H to make (N-L+(N<L)*H)%H+L, as C seems to be defined such that true=1 and false=0. It works well enough for me, and seems to answer the original question neatly. If anyone knows how to do it without the MOD operator % to make it dazzlingly fast, please do it. I don't need speed right now, but some time I will, no doubt.

EDIT:

That function fails if N is lower than L by more than H-L+1 but this doesn't:

int Wrap(N,L,H){
  H-=L; return (N-L+(N<L)*((L-N)/H+1)*++H)%H+L;
}

I think it would break at the negative extreme of the integer range in any system, but should work for most practical situations. It adds an extra multiplication and a division, but is still fairly compact.

(This edit is just for completion, because I came up with a much better way, in a newer post in this thread.)

Crow.

回答5:

Actually, since -1 % 4 returns -1 on every system I've even been on, the simple mod solution doesn't work. I would try:

int range = kUpperBound  - kLowerBound +1;
kx = ((kx - kLowerBound) % range) + range;
return (kx % range) + kLowerBound;

if kx is positive, you mod, add range, and mod back, undoing the add. If kx is negative, you mod, add range which makes it positive, then mod again, which doesn't do anything.

回答6:

Personally I've found solutions to these types of functions to be cleaner if range is exclusive and divisor is restricted to positive values.

int ifloordiv(int x, int y)
{
    if (x > 0)
        return x / y;
    if (x < 0)
        return (x + 1) / y - 1;
    return 0
}

int iwrap(int x, int y)
{   return x - y * ifloordiv(x, y);
}

Integrated.

int iwrap(int x, int y)
{
    if (x > 0)
        return x % y;
    if (x < 0)
        return (x + 1) % y + y - 1;
    return 0;
}

Same family. Why not?

int ireflect(int x, int y)
{
    int z = iwrap(x, y*2);
    if (z < y)
        return z;
    return y*2-1 - z;
}

int ibandy(int x, int y)
{
    if (y != 1)
        return ireflect(abs(x + x / (y - 1)), y);
    return 0;
}

Ranged functionality can be implemented for all functions with,

// output is in the range [min, max).
int func2(int x, int min, int max)
{
    // increment max for inclusive behavior.
    assert(min < max);
    return func(x - min, max - min) + min;
}

回答7:

I would suggest this solution:

int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
    int d = kUpperBound - kLowerBound + 1;
    return kLowerBound + (kX >= 0 ? kX % d : -kX % d ? d - (-kX % d) : 0);
}

The if-then-else logic of the ?: operator makes sure that both operands of % are nonnegative.

回答8:

I would give an entry point to the most common case lowerBound=0, upperBound=N-1. And call this function in the general case. No mod computation is done where I is already in range. It assumes upper>=lower, or n>0.

int wrapN(int i,int n)
{
  if (i<0) return (n-1)-(-1-i)%n; // -1-i is >=0
  if (i>=n) return i%n;
  return i; // In range, no mod
}

int wrapLU(int i,int lower,int upper)
{
  return lower+wrapN(i-lower,1+upper-lower);
}

回答9:

An answer that has some symmetry and also makes it obvious that when kX is in range, it is returned unmodified.

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

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

    if (kX > kUpperBound)
        return kX - range_size * ((kX - kUpperBound) / range_size + 1);

    return kX;
}

回答10:

I've faced this problem as well. This is my solution.

template <> int mod(const int &x, const int &y) {
    return x % y;
}
template <class T> T mod(const T &x, const T &y) {
    return ::fmod((T)x, (T)y);
}
template <class T> T wrap(const T &x, const T &max, const T &min = 0) {
    if(max < min)
        return x;
    if(x > max)
        return min + mod(x - min, max - min + 1);
    if(x < min)
        return max - mod(min - x, max - min + 1);
    return x;
}

I don't know if it's good, but I'd thought I'd share since I got directed here when doing a Google search on this problem and found the above solutions lacking to my needs. =)

回答11:

My other post got nasty, all that 'corrective' multiplication and division got out of hand. After looking at Martin Stettner's post, and at my own starting conditions of (N-L)%H+L, I came up with this:

int Wrap(N,L,H){
  H=H-L+1; N=(N-L)%H+L; if(N<L)N+=H; return N;
}

At the extreme negative end of the integer range it breaks as my other one would, but it will be faster, and is a lot easier to read, and avoids the other nastiness that crept in to it.

Crow.

回答12:

For negative kX, you can add:

int temp = kUpperBound - kLowerBound + 1;
while (kX < 0) kX += temp;
return kX%temp + kLowerBound;

回答13:

Why not using Extension methods.

public static class IntExtensions
{
    public static int Wrap(this int kX, int kLowerBound, int kUpperBound)
    {
        int range_size = kUpperBound - kLowerBound + 1;

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

        return kLowerBound + (kX - kLowerBound) % range_size;
    }
}

Usage: currentInt = (++currentInt).Wrap(0, 2);