Wrap unsigned integer addition/subtraction around a range

Question

I am in need a of a function that computes the sum of unsigned val and signed dX and wraps the result around the range lower and upper

For example:

A value of 5, change of -6, and a range of 0 and 10 would return 10.

< 1 2 3 4 5 6 7 8 9 10 >

A value of 2, change of 3, and range of 1 and 3 would return 2

/*
 * Given a value and a change in that value (dX), find the sum and wrap it between lower and upper.
 */
unsigned int wrap(unsigned int val, const int dX, const unsigned int lower, unsigned int upper)
{

}

I don't really know how to approach the unsigned and signed addition/subtraction to avoid underflow. Nor am I sure exactly how to wrap the lower bound.

It's not an assignment. It's for my own personal project. Don't downvote assuming I'm just asking for my homework to be completed. There are [similar questions on stack overflow](http://stackoverflow.com/questions/2061245/how-to-subtract-two-unsigned-ints-with-wrap-around-or-overflow) but they don't directly address underflow along with wrapping — Hatefiend, Mar 22 '17 at 01:23
@BLUEPIXY that won't work because the **sum** you do with `int calc = val + dx;` is `signed`. Meaning if the sum would have been over signed integer max value, it would overflow to negative values. I've already though about that and hence that's why I'm here on stack overflow — Hatefiend, Mar 22 '17 at 01:30
I think that `long long` can be used for calculation in the middle. — BLUEPIXY, Mar 22 '17 at 01:34
That seems a little bit of a hack-y solution but I think you are correct. Hmmmmm — Hatefiend, Mar 22 '17 at 01:35
Do you have to handle the case where upper - lower is greater than the maximum signed integer value? — samgak, Mar 22 '17 at 01:50
@samgak No that shouldn't happen unless the bounds are ridiculously high. — Hatefiend, Mar 22 '17 at 01:52

samgak · Answer 1 · 2017-03-22T02:49:57.383

2

First, calculate upper-lower to use as a modulus value and convert to an int (as per your comment, the case where upper - lower is greater than the maximum signed integer value doesn't need to be handled):

int modulus = (int)(upper - lower) + 1;

You can then modulo dX by the modulus, to take into account wrapping around:

dX %= modulus;

dX will now have a value between -(modulus-1) and modulus-1. If it's negative just add the modulus:

if(dX < 0)
    dX += modulus;

dX is now guarantted to be positive and you only have to handle the overflow. You can add the difference between val and lower, and then check against the modulus again. This avoids having to deal with unsigned overflow.

dX += (val - lower);
if(dX >= modulus)
    dX -= modulus;

This gives you a value relative to the lower bound, which you can use to compute the new val:

val = lower + (unsigned int)dX;

edited Mar 22 '17 at 02:49

answered Mar 22 '17 at 02:03

samgak

23,944
4
60
82

Wow, what an answer. I like the logic of lowering `dX` down to only the part that matters. I think though that you need to add `+ 1` to `(int)(upper - lower)` or else it seems to be one under the upper bound. For example, `wrap(0, -1, 0, 10)` prints `9` instead of `10` which it should have wrapped to. – Hatefiend Mar 22 '17 at 02:42
Note that `upper - lower` may exceed `INT_MAX` rendering `int modulus = (int)(upper - lower)` problematic. – chux - Reinstate Monica Mar 22 '17 at 02:45
@Hatefiend Yes, you're right, I didn't notice that the upper bound was inclusive. I've edited the answer to add 1 to the modulus – samgak Mar 22 '17 at 02:51

ad absurdum · Accepted Answer · 2017-03-22T03:01:51.557

If you are willing to change dx from const int to int, you can do the arithmetic in a loop. This avoids possible problems with upper - lower exceeding INT_MAX.

#include <stdio.h>

unsigned int wrap_add(unsigned int val,
                      int dx,
                      const unsigned int lower,
                      const unsigned int upper);

int main(void)
{
    printf("Range [0, 10]: 5 + (-6) = %u\n", wrap_add(5, -6, 0, 10));
    printf("Range [1, 3]: 2 + 3 = %u\n", wrap_add(2, 3, 1, 3));
    printf("Range [2, 5]: 2 + (-9) = %u\n", wrap_add(2, -9, 2, 5));

    return 0;
}

unsigned int wrap_add(unsigned int val,
                      int dx,
                      const unsigned int lower,
                      const unsigned int upper)
{
    while (dx < 0) {
        if (val == lower) {
            val = upper;
        } else {
            --val;
        }
        ++dx;
    }

    while (dx > 0) {
        if (val == upper) {
            val = lower;
        } else {
            ++val;
        }
        --dx;
    }

    return val;
}

Program output:

Range [0, 10]: 5 + (-6) = 10
Range [1, 3]: 2 + 3 = 2
Range [2, 5]: 2 + (-9) = 5

I guess looping is the only way to gain true safety from under flowing? Great solution. I'll definitely use this one. Thanks so much. — Hatefiend, Mar 22 '17 at 03:06
I don't know if it is the only way, but it seemed like a nice alternative. If the range is very large, the loops will be large, and this may be too inefficient for large numbers of calculations. I suppose the best solution always depends on the context. — ad absurdum, Mar 22 '17 at 03:10

Wrap unsigned integer addition/subtraction around a range

2 Answers2