CODEWITHSUNDEEP
c++calgorithm
Hatefiend
Hatefiend

Reputation: 3596

Wrap unsigned integer addition/subtraction around a range

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.

Upvotes: 0

Views: 1658

Answers (2)

ad absurdum
ad absurdum

Reputation: 21323

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

Upvotes: 2

samgak
samgak

Reputation: 24417

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;

Upvotes: 2

Related Questions