Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Integer subtraction with wrap around for N bits

Basically, the behavior you get when overflowing integers with subtraction, but for a given number of bits. The obvious way, assuming a signed integer:

template <int BITS>
int sub_wrap(int v, int s) {
  int max = (1<<(BITS));
  v -= s;
  if (v < -max) v += max*2;
  // or if branching is bad, something like:
  // v += (max*2) * (v < -max)
  return v;
}

// For example subtracting 24 from -16 with 5 bit wrap,
// with a range of -32, 31
sub_wrap<5>(-16, 28); -> 20

Is there a neat way of doing it that is less ugly and preferably faster than the one above?

UPDATE: Sorry about the confusion. I thoughtlessly included the confusing notation of using the number of bits excluding the sigh bit. So in the above, replace 5 bits with 6 bits for a lot more sanity.

like image 312
porgarmingduod Avatar asked Nov 29 '11 10:11

porgarmingduod


People also ask

How does unsigned subtraction work?

By casting the two numbers to unsigned, we ensure that if b > a, the difference between the two is going to be a large unsigned number and have it's highest bit set. When translating this large unsigned number into its signed counterpart we will always get a negative number due to the set MSB.

What is wrap around in C?

An integer overflow or wraparound occurs when an integer value is incremented to a value that is too large to store in the associated representation. When this occurs, the value may wrap to become a very small or negative number.

Can you subtract an INT from a float?

C++ Subtraction of Floating Point Number from IntegerYou can subtract an integer and floating point number using subtraction operator.

Can you subtract a long from an int?

Yes you can. The int will be converted by the usual arithmetic conversions to a long long int for the sake of the subtraction, so that both operands have the same integer conversion rank, and the result will also be a long long int .


1 Answers

For unsigned arithmetic, and mask the results, e.g.:

template<int bits>
unsigned
sub_wrap( unsigned v, unsigned s )
{
    return (v - s) & ((1 << bits) - 1);
}

More generally, you can use the modulo operator:

template<int modulo>
unsigned
sub_wrap( unsigned v, unsigned s )
{
    return (v - s) % modulo;
}

(Wrapping on n bits is the equivalent of modulo 2^n.)

For signed arithmetic, it's a bit more complex; using the mask, you'll have to sign extend the results (supposing 2's complement).

EDIT: Using sehe's suggestion for signed arithmetic:

template<int bits>
int
sub_wrap( int v, int s )
{
    struct Bits { signed int r: bits; } tmp;
    tmp.r = v - s;
    return tmp.r;
}

Given this, sub_wrap<5>( -16, 28 ) gives -12 (which is correct—note that 28 cannot be represented as signed int in 5 bits); sub_wrap<6>( -16, 28 ) gives 20.

like image 174
James Kanze Avatar answered Sep 25 '22 06:09

James Kanze