A clean, efficient algorithm for combining integers in C ++

Question

/** * Returns a number between kLowerBound and kUpperBound * eg: Wrap(-1, 0, 4); // Returns 4 * eg: Wrap(5, 0, 4); // Returns 0 */ int Wrap(int const kX, int const kLowerBound, int const kUpperBound) { // Suggest an implementation? } 

Answer 1

The sign a % b is determined only if a and b are 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; } 

Answer 2

The following should work regardless of the implementation of the mod statement:

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

The advantage over other solutions is that it uses only one% (for example, division), which makes it quite effective.

Note (Off Topic):

This is a good example of why it is sometimes wise to define intervals whose upper bound is the first element outside the range (for example, for STL iterators ...). In this case, both +1s will disappear.

Answer 3

The fastest solution, the least flexible: use your own data types that will wrap the hardware.

The absolute fastest method for integers will be to have your data scaled to int8 / int16 / int32 or any other native data type. Then, when you need your data to transfer your own data type, it will be done at the hardware level! Very painless and an order of magnitude faster than in the case of the implementation of software packaging, visible here.

As an example of an example:

I found this to be very useful when I need a quick implementation of sin / cos, implemented using a look-up table to implement sin / cos. Basically, you scale your data so that INT16_MAX is pi and INT16_MIN is -pi. Then you have to go.

As a side note, scaling up your data will add some final computational overhead, which usually looks something like this:

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

Feel free to swap int for something else you want, e.g. int8_t / int16_t / int32_t.

---

The next fastest solution, more flexible: the mod operation is slower, if possible, try using bit masks!

Most of the solutions I'm looking at are functionally correct ... but they depend on how the mod works.

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

If you can scale your data to two, then you can use a bitmask that will execute in one cycle (on 99% of all platforms) and your speed increase will be about one order of magnitude (at least 2 or 3 times faster) .

C code for packaging implementation:

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

Remember to make #define something run-time. And feel free to tweak the bit mask to be any power of the two you need. Like 0xFFFFFFFF or the power of two that you decide to implement.

---

ps I highly recommend reading fixed-point processing information when you mess with wrapping / overflow conditions. I suggest reading:

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

Answer 4

Please do not forget about this post. :)

It's 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 if L is less than H.

Background ... (Note that H uses a reusable variable here; it is set to the original H-L+1 ).

I used (NL)%H+L when building, but unlike Lua, which I used before starting to learn C a few months ago, this would NOT work if I used inputs below the lower bound, not to mention negative entrances. (Lua is built in C, but I don’t know what it does, and it most likely will not be fast ...)

I decided to add +(N<L)*H to make (N-L+(N<L)*H)%H+L , since C seems to be defined such that true = 1 and false = 0. It works good enough for me and seems to answer the original question neatly. If someone knows how to do this without the MOD statement, to make it dazzlingly fast, please do it. I don’t need speed now, but after a while I will undoubtedly be.

EDIT:

This function fails if N lower than L more than H-L+1 , but it is not:

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

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

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

Crow

Answer 5

Actually, since -1% 4 returns -1 for every system that I was even on, a simple solution for modems does not work. I would try:

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

if kx is positive, you will change the mod, add a range and change the style back by canceling the add. If kx is negative, you are mod, add a range that makes it positive, and then mod again, which does nothing.

Answer 6

Personally, I found the solutions for these types of functions cleaner if the range is exclusive and the divisor is limited 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; } 

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

Range functionality can be implemented for all functions using

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

Answer 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 ensures that both % operands are non-negative.

Answer 8

The answer, which has some symmetry, and also makes it obvious that when kX is in the range, it returns 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; } 

Answer 9

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 calculation is performed when I'm 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); } 

Answer 10

I ran into this problem. This is my decision.

 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 this is good, but I thought I would share it since I was sent here when I do a Google search on this issue and find that the above solutions do not meet my needs. =)

Answer 11

My other post got nasty, all that “corrective” multiplication and division went out of control. Looking at the post of Martin Stetner and in my initial conditions (NL)%H+L , I came up with the following:

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

At the extreme negative end of the integer range, it breaks, like my other, but it will be faster and much easier to read, and avoid the other muck that has crept up to it.

Crow

Answer 12

For negative kX you can add:

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

Answer 13

Why not use 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);