Integer subtraction with wrap around for N bits

Question

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.

That depends entirely on your point of view. I'm just used to denoting the number of bits excluding the sign in the code I'm currently using, but I guess that is just confusing. — porgarmingduod
– porgarmingduod, Commented Nov 29, 2011 at 14:35

James Kanze · Accepted Answer · 2011-11-29 11:28:31Z

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.

Your code never produces negative values, which seems to be what the OP wants.
@Alex Judging from his example, that's what he wants, but according to what he wrote, it's not clear. My code is what I would consider the "classical" solution, for modulo arithmetic over a range [0,2^n), but for modulo arithmetic, I would use unsigned integral types. @sehe's suggestion is, however, quite clever, and works for signed types as well.
+1 for trying some more and (a) pointing out that I should not have taken the sample from the OP at face value (b) showing that bitfields can be varied based on a const template argument (weehoo: never underestimate the power of C++)
@JamesKanze: from the OP's code it follows that the resultant range is expected to include negative numbers as well. See if (v < -max) v += max*2;.
Thanks for this clean answer, and sorry for the confusing example. I put up another question regarding how this will perform.

sehe · Accepted Answer · 2011-12-04 01:05:54Z

I suppose this should work:

 struct bits { signed int field : 5; }; bits a = { -16 }; bits b = { 28 }; bits c = { a.field - b.field }; std::cout << c.field << std::endl;

~~I'm pretty sure the field width won't work with a const template argument... and hence this is less generic. It should, however, avoid manual tinkering. Will post test soon~~

Update It turns out my answer wasn't incorrect after all. It is just that the sample input (28) cannot be represented in 5 bits (signed). The outcome of the above is -12 (see http://ideone.com/AUrXy).

Here is, for completeness, a templated version after all:

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

On the other hand, assigning back and then returning the field from the struct would work. This may be the simplest solution for signed values.
@JamesKanze: I don't know what exactly you meant, but this seems to indicate it wouldn't work: ideone.com/AUrXy
As written, it won't work, but if you declare the bit field signed int, assign the computed value back into it, and then return the value from the bit field, it should work (and does for me).
Whether bit fields are signed or unsigned by default is implementation defined.

Alexey Frunze · Accepted Answer · 2011-11-29 12:47:12Z

Here's how I'd do it w/o conditional branches and multiplication:

#include <stdio.h> // Assumptions: // - ints are 32-bit // - signed ints are 2's complement // - right shifts of signed ints are sign-preserving arithmetic shifts // - signed overflows are harmless even though strictly speaking they // result in undefined behavior // // Requirements: // - 0 < bits <= 32 int sub_wrap(int v, int s, unsigned bits) { int d = v - s; unsigned m = ~0u >> (32 - bits); int r = d & m | -((d >> (bits - 1)) & 1) & ~m; return r; } #define BITS 2 int main(void) { int i, j; for (i = -(1 << (BITS - 1)); i <= (1 << (BITS - 1)) - 1; i++) for (j = -(1 << (BITS - 1)); j <= (1 << (BITS - 1)) - 1; j++) printf("%d - %d = %d\n", i, j, sub_wrap(i, j, BITS)); return 0; }

Output:

-2 - -2 = 0 -2 - -1 = -1 -2 - 0 = -2 -2 - 1 = 1 -1 - -2 = 1 -1 - -1 = 0 -1 - 0 = -1 -1 - 1 = -2 0 - -2 = -2 0 - -1 = 1 0 - 0 = 0 0 - 1 = -1 1 - -2 = -1 1 - -1 = -2 1 - 0 = 1 1 - 1 = 0

hochl · Accepted Answer · 2011-11-29 11:15:50Z

This simulates an n bit integer operation:

#include <iostream> #include <cstdlib> template< typename T > T sub_wrap(T a, T b, int nBits) { T topBit, mask, tmp; topBit=T(1) << (nBits-1); mask=(topBit << 1)-1; tmp=((a&mask)+((~b+1)&mask))&mask; if (tmp & topBit) tmp=-((~tmp&mask)+1); return tmp; } int main(int argc, char* argv[]) { std::cout << sub_wrap< int >(atoi(argv[1]), atoi(argv[2]), atoi(argv[3])) << std::endl; return 0; }

Results:

$ ./sim 5 6 4 -1 $ ./sim 7 3 4 4 $ ./sim 7 -1 4 -8 $ ./sim -16 28 4 4 $ ./sim -16 28 5 -12 $ ./sim -16 28 6 20

Seems you miscalculated your type size by 1 bit.

Collectives™ on Stack Overflow

Integer subtraction with wrap around for N bits

4 Answers 4

5 Comments

7 Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

5 Comments

7 Comments

Comments

Comments

Linked

Related