# On a modern compiler, how do I intentionally code for 2s complement with wraparound?

I want to compare sequence numbers (given to this code from elsewhere) that may wrap around. Simply comparing two such values will not handle the case like 0x00000002 being greater than 0xfffffffd, but I can assume that the numbers being compared are close together, not nearly 4 billion apart.

I get the desired result efficently if, rather than comparing, I subtract, allowing two's complement wrap-around, and then interpreting the difference as signed. In fact, I would hope that the final test (for branching) against 0 will be no extra cost as the subtraction already set the flags.

My question concerns the presence of undefined behavior in C++11 and later. How do I write this so it does what I said, rather than the optimizer possibly trashing the code, perhaps assuming that the result is never negative.

The straightforward code would be:

``````bool seq_ordered (uint32_t a, uint32_t b)
{
auto delta = int32_t (b-a);
return delta > 0;
}
``````

Would it be better to do the initial subtraction while interpreting the arguments as signed or unsigned? Is there a modern idiom to provide for wrapping arithmetic?

• It's often important to be careful with the types of numeric literals (e.g. use `0u` rather than `0`, or use `UINT32_C` etc), but your `0` above is OK.
– user8709
Commented May 30, 2016 at 3:20

(Disclaimer: I am not an expert in undefined behavior. But I believe I know just enough to give an answer to this question.)
(Disclaimer: Length of answer is not an indication of correctness.)
(More disclaimer: It appears that Daniel Jour's answer handles a condition that I didn't (nor does OP's version): when `(b-a) == 0x80000000`. The significance is that neither OP's or my version of code can be used safely as a sorting predicate, which requires tie-breaking. Sorting modular numbers is a topic in itself and the existence of an answer is data-dependent.)

``````// OP's original code
bool seq_ordered (uint32_t a, uint32_t b)
{
auto delta = int32_t (b-a);
return delta > 0;
}
``````

I think your code is fine as-is. It makes two assumptions, but both assumptions should be fine.

• The source values `a` and `b` are correctly encoded in binary scaling, which is compatible with two's complement.
• The C++ target platform uses two's complement.

You should be careful regarding the first point (the source values), especially if they are generated by hardware (such as rotary encoder). Although it is practical to assume that most C++ targets use two's complement, analog-to-digital devices are not part of your "computer environment". Check the documentation of the electronic component.

Guarding against the second point is simple: use a `static_assert` so that the code will not compile on targets that do not use two's complement.

``````static_assert((uint32_t)(-1) == (uint32_t)0xFFFFFFFFuL, "Invalid arithmetic unless target uses two's complement");
``````

Explanation: (according to my understanding)

• Subtraction between two `uint32_t` obeys modulo 232
• Conversion from `uint32_t` into `int32_t` is implementation-defined. It is specifically not undefined. Typically this means it is dependent on whether the target uses two's complement or not.
My opinion is that it is practical to assume it and then guard against using `static_assert`.
• If the two preceding steps were correct, the comparison is performed in `int32_t` and should yield the mathematically correct result.

If you do not like the conversion into `int32_t` at all, but are comfortable with the practical assumption of two's complement, then you can avoid the conversion as follows:

``````// I think it should give mathematically identical result, no?
bool seq_ordered(uint32_t a, uint32_t b)
{
uint32_t diff = (b - a);
return (diff > 0uL) && (diff < 0x80000000uL);
}
``````

(Disclaimer: based on my testing with a few online C++ compilers, the x86-64 disassembly generated from my version is different from OP's version. Specifically, my version results in two comparisons, whereas OP's version results in one comparison.)

The following links are provided for reference. As I said I'm not expert in this, so I cannot guarantee the correctness of my own answer.

• Thanks in particular for the links. Your explaination details what I need to know, and it's good to see where that is in the spec rather than just having it repeated. But, you cite the C rules for overflow. Is C++11 different? Does it depend on the type (C likes to do + and - after promotions, while c++ defines them for each integral type). Commented May 30, 2016 at 0:46
• OP's code is not fine. "Conversion from `uint32_t` into `int32_t` is implementation-defined [..]" if the result is in the range of representable value of `int32_t`. Otherwise it's an integer overflow and thus undefined behaviour. Why use a "magic value" 0x80000000 instead of calculating it as "half of the range" (`(UINT32_MAX + 1) / 2`, note: not the real calculation)? Commented May 30, 2016 at 10:10
• Sorry, my first remark was wrong. You're right, it's in fact implementation defined. But why the magic value? Commented May 30, 2016 at 10:17
• @DanielJour I actually intended to give you the credit which you deserved, but I am not confident enough to analyze your code (since it is a bit long) to say that it is correct for all situations for which it will compile. (In fact I'm surprised that someone had downvoted yours.) I am intentional in limiting my answer to one type (`uint32_t`) and to constant values (i.e. I am refraining from generalizations) as I try to analyze the situation (according to the rules). Expert practitioners can certainly make bigger leaps than I do. (Edited: to counteract the undeserved -1, I have now +1 yours.) Commented May 30, 2016 at 10:51
• @rwong I think that's a good choice. I generalized it because I'm confident of the underlying mathematical "operations", but that's of course not needed if only `uint32_t` is of interest. You could add a sentence about why it's the value `0x80000000` though (otherwise it's a bit hard to understand). Commented May 30, 2016 at 10:57

You're working on the wrong level here. You should simply `return b > a`. Writing a function that's correct in all cases is going to be exceptionally difficult and nearly everybody gets it wrong and has a bunch of subtle UB in their codebase. And that's before trying to get it as fast as the compiler.

Or in simple terms, the answer to your question is "You don't".

The only way this can work is to use a builtin compiler feature, like a builtin function or a compiler flag like -fwrapv. These do not exist for all compilers.

• I disagree. "You don't" is the best choice when there's an already working implementation, for example provided by the compiler. But somebody had to write this, too. Which is going to be you if the environment you're targeting doesn't provide such functionality. It's really difficult, true. One can easily miss cases of undefined behaviour, true (if you find one in my answer, please let me know). Moreover, there's also the possibility to write the required code in the assembly language of the target. Commented May 29, 2016 at 10:31
• They didn't have to write that, because they were under different constraints- they can make assumptions that you never can. Also, writing the function in the assembly language of the target is basically admitting defeat, since the question is in C++, Commented May 30, 2016 at 11:47
• I think the intention was to define a non-transitive wrapping relation so that 0xAAAAAAAA would compare greater than 0x55555555, and 0x00000000 would compare greater than 0xAAAAAAAA, but 0x55555555 would compare greater than 0x00000000. Commented Jul 6, 2016 at 21:29
• I assumed sequence numbers that are incremented all the time and eventually wrap around - but really old ones will not be in use anymore. Say it takes a year to wraparound, but we never compare sequence numbers more than a week apart. Around the time of the wraparound newer sequence ids would be less than much older ones. Commented Oct 10, 2021 at 22:06

You have no undefined behaviour as long as you stay within unsigned integers.

Just writing what I think you want to achieve: You have 32 bit sequence numbers that will be incremented. After a long long time this will wrap around. However, we assume that no sequence number is ever compared to a sequence number that is 2^31 or more away.

``````uint32_t seq1 = ...;
uint32_t seq2 = ...;
uint32_t diff = seq1 - seq2;

if (diff < ((uint32_t)1) << 31) {
// seq1 was created (diff) steps later than seq2
} else {
diff = -diff;
// seq1 was created (diff) steps earlier than seq2
}
``````

Totally portable, and not one bit of undefined behaviour in sight. One's complement, two's complement, signed magnitude, all doesn't matter. Correct as long as you never compare any sequence numbers that were created 2^31 or more steps apart. But that's not a big problem, because if seq1 was created 2^32 steps later than seq2, they would be identical and your code couldn't possible work.

If the range of 2^31 is not enough, you use 64 bit integers and just compare with >, ==, <. And then you calculate how much time it would take to make your code misbehave. For example if increasing the sequence number requires also taking some action which takes 100 nanoseconds, you can do this 10^7 times per second, 3*10^14 times per year, about 250,000 years until a signed 64 bit integer overflows.

• But your code returns the absolute value, or the symmetric difference, and does not show the relative ordering. That's not the same thing. If we just wanted to know if they were different (diff == 0) then just writing `if (seq1!=seq2)` would have been enough. It's not doing the same thing as the original. Commented Oct 11, 2021 at 15:35
• My code doesn’t return anything. It has an if-branch for one order and an else-branch for another case. Commented Oct 14, 2021 at 5:48
• OK, "produces as a result" rather than an actual `return`. Commented Oct 14, 2021 at 14:10

The C++ standard has improved since the question was posted, to reflect the fact that all modern architectures are 2s complement. The latest standard, as I write this now (C++20), states that:

• unsigned arithmetic will have addition and subtraction wrap around, so it's modulo 2n.
• casting signed to unsigned will turn negative numbers into 2s complement.
• casting unsigned to signed is implementation defined.

This is summarized on Cppreference under Integer conversions and arithmetic.

That last point is still an issue. Given `int32_t (b-a)` the subtraction does what I want for sure, but casting to `int` is not guaranteed. This could be addressed by doing the "conversion" explicitly, checking for the high bit set and doing arithmetic to get the final answer. But testing the input values instead is simpler:

``````if (b>a)  return int32_t(b-a);
else return -int32_t(a-b);
``````

Although I think any platform that did distinguish signed and unsigned values at the register level and raised exceptions for out-of-range would have a lot of compatibility issues with real code if that feature was left on by default! The compiler would probably have some kind of pragma to control it.

• "unsigned arithmetic will be 2s complement." - "'s complement is a way of representing negative numbers. This statement makes no sense. Commented Oct 10, 2021 at 21:55
• @SebastianRedl I fixed it, thanks. Commented Oct 11, 2021 at 15:29

TL;DR version:

Since there's no such thing as overflow / underflow with `unsigned` data types in C++ you can safely calculate a difference between your two values. The size of this difference in relation to the range of possible values indicates which value is less than the other:

``````template<bool Strict = true, typename T>
bool ordered(T assumed_smaller, T assumed_larger) {
static_assert(std::is_unsigned<T>::value, "Need unsigned");
// Calculate the half of the range of the type, by using it's bit width.
constexpr T const half_range = 1u << ((sizeof(T) * CHAR_BIT) - 1);
// Calculate difference, possibly with wrap around.
T const difference = assumed_larger - assumed_smaller;
bool const not_equal = difference != 0;
if (Strict) {
// Strict mode, disallow ordered(a,b) and ordered(b,a) to be both true
return not_equal
&& ((difference < half_range)
|| ((difference == half_range)
&& (assumed_smaller < assumed_larger)));
} else {
// Non-strict, both ordered(a,b) and ordered(b,a) are true
// if they're half_range apart.
return not_equal && (difference <= half_range);
}
}
``````

A bit more detail:

Assuming 2 bit unsigned integers (thus 0 to 3 as possible values), one has the following cases:

``````0 0 | false
0 1 | true
0 2 | true
0 3 | false

1 0 | false
1 1 | false
1 2 | true
1 3 | true

2 0 | false (0 2 is already true)
2 1 | false
2 2 | false
2 3 | true

3 0 | true
3 1 | false (1 3 is already true)
3 2 | false
3 3 | false
``````

`true` means the first value on the line is to be considered "coming before" the second value. One can better imagine this when viewing the possible values arranged in a kind of a circle (since we want to allow wrapping):

``````  0
3   1
2
``````

Two values are in the correct order if we can get from the assumed smaller one to the other one - going clockwise - in no more than 2 steps. Thus `3 0` are in the correct order, but `3 2` are not.

To accomplish this, one just needs to check whether `assumed_larger - assumed_smaller <= 2` (where 2 is half of `max_value + 1`, or `2^(bits-1)`). This difference is the number of steps in clockwise direction if `assumed_larger` >= `assumed_smaller` and in counter-clockwise direction otherwise (thanks to modulo, example: `0 - 3 = -3 = -3 + 4 = 1 (mod 4)`).

This leaves the following issue: `0 2` and `2 0` (as well as `1 3` and `3 1`) both require 2 steps, thus with the above test both would be in the correct order, which is a violation of the expectation that "if `a != b`, then either `a` before `b` or `b` before `a`.

Since the question states that the values won't be "far apart", this wouldn't be an issue, but to correct it one needs to handle the case `assumed_larger - assumed_smaller == 2` specially by actually comparing both values.

``````bool seq_ordered(uint32_t assumed_smaller, uint32_t assumed_larger) {
constexpr uint32_t const half_range = 1 << ((sizeof(uint32_t) * CHAR_BIT) / 2);
uint32_t difference = assumed_larger - assumed_smaller;
return (difference != 0)
&& ((difference < half_range)
|| ((difference == half_range)
&& (assumed_smaller < assumed_larger)));
``````
• Thanks. Why not just use strick < rather than <= and avoid the separate test for equality? Commented May 29, 2016 at 7:26
• @JDługosz Because with `<` you'll get incorrect result for `assumed_smaller == 0`. Commented May 29, 2016 at 7:37
• @JDługosz Wait a second ... assuming 2 bit unsigned integers (0 - 3), what should `seq_ordered(0, 3)` return? Commented May 29, 2016 at 7:38
• The Q states that the delta will be small compared to the range of the type. So this should be false, since -1 has a smaller absolute value than +3. Using the original code posted, with 2 bit types, produces this result. With your code, 3 <= 3 requires 3!=3 to veto it, but writing 3 < 3 would also work to produce false. Commented May 29, 2016 at 7:52
• This isn't correct - you've performed the subtraction then checked for over/underflow, which is illegal. Commented May 29, 2016 at 9:29