3 ms·
We can take advantage of two's complement arithmetic, plus the knowledge that the overflow flag is the xor of the carry into the sign bit with the carry out of
by pbsd 12y ago
We can take advantage of two's complement arithmetic, plus the knowledge that the overflow flag is the xor of the carry into the sign bit with the carry out of the sign bit, to devise a simple expression:
int checked_add_n(int_t a, int_t b, int_t *rp) {
uint_t s = (uint_t)a + (uint_t)b;
*rp = s;
return ((a ^ s)&(b ^ s)) >> (BITS - 1);
}
This is essentially doing the same thing as checked_add_3. First, we extract the carry into the sign bit with
ci = s ^ a ^ b; // upper bit of ci contains the relevant bit
Carry out can be found via the usual majority expression:
co = ci&a ^ ci&b ^ a&b;
Xoring the two, and simplifying using De Morgan's laws and their relatives results in the expression above.
Although the metric is far from optimal, clang gives me 6 arithmetic instructions (minus the ret): http://goo.gl/Amdo93 http://goo.gl/Amdo93
- torrent-of-ions 12y agoYou can't take advantage of two's complement arithmetic if you want portable C, though.
- userbinator 12y agoAre there any machines in widespread use today that don't use two's complement? I guess if there were, we'd hear a lot more about this issue... I know that some mainframes are an example, but they're somewhat of a niche.
- nitrogen 12y agoSigned integer overflow is undefined in C, so optimizers can do really weird things to code that has overflows.
- anaphor 12y agoYes, see: http://people.csail.mit.edu/nickolai/papers/wang-undef.pdf http://people.csail.mit.edu/nickolai/papers/wang-undef.pdf
- kps 12y agoAnd see John Regehr's ( http://blog.regehr.org/ http://blog.regehr.org/, of the headline article) other posts. He's written a great deal about undefined behaviour in C/C++ and how modern compilers handle it. Check the ‘Compilers’ and ‘Software Correctness’ categories.
- stephencanon 12y agoMinor nit: the result of converting an unsigned integer to signed is implementation-defined if the unsigned value cannot be represented in the destination type. This can be fixed with the following bizarre expression: *rp = s <= INTN_MAX ? s : (intN_t)(s + INTN_MIN) + INTN_MIN; "What the hell?” I hear the internet ask. if s <= INTN_MAX, then the result is representable as an intN_t, so we’re fine; otherwise s + INTN_MIN is guaranteed* to be representable as an intN_t, and the second addition of INTN_MIN “completes" the twos-complement (no-op) conversion to signed. “But you can’t assume that the signed type is twos complement!” an actually of pedants responds. Fortunately, the <stdint.h> intN_t types, if they exist, are required to be twos-complement. “But more operations and—oh-horrors-a-branch!” say the premature optimizers. Not to fear. Compilers are smart. Both gcc and clang are happy to look through this and no-op the whole thing away. [*] for the <stdint.h> intN_t types, which are twos-complement with no padding.