# Unsigned 64bit subtract-with-borrow in Standard C++

I'm writing a (compile-time-)fixed-width unsigned big integer. To implement subtraction, a subtract-with-borrow primitive is required. When efficient platform-specific implementation isn't available (e.g. x86_64's _subborrow_u64 intrinsic), it needs to be implemented in Standard C++.

I've been able to come up with the following implementation:

#include <stdint.h>

inline
auto subtract_with_borrow(
uint64_t& result,
uint64_t left, uint64_t right,
uint64_t borrow /* only 0 or 1 */)
-> uint64_t /* borrow */
{
result = left - right - borrow;
return (left < right) | ((left == right) & borrow);
}


However, I suspect it might be suboptimal since it requires roughly twice as many operations as add-with-carry (don't review it):

inline
auto add_with_carry(
uint64_t& result,
uint64_t left, uint64_t right,
uint64_t carry /* only 0 or 1 */)
-> uint64_t /* carry */
{
result = left + right;
uint64_t next_carry = result < left;
result += carry;
return next_carry;
}


I intuitively expect a certain symmetry to exist here. Can subtract_with_borrow be simplified further? Or is my intuition wrong and this is indeed the optimal implementation?

And no, the compiler optimization doesn't manage to magically transform it into a better version.

## 2 Answers

Your intuition is correct, but the issue is that your add_with_carry lacks the carry propagation in subtract_with_borrow.

That's a general observation - if the new code looks more complicated than the old code, you should also consider that the old code lacked something.

Consider the call add_with_carray(0,2^64-1,1):

  result=0+(2^64-1); // 2^64-1
next_carry=(2^64-1)<0; // False
result+=1; // causing result=0; due to overflow
return next_carry; // 0


In general you should test such routines for carry=0,1 and left, right close to 0 and 2^64-1

Prefer to use the C++ <cstdint> header that puts identifiers in the correct namespace, rather than the deprecated C-compatibility header. This is particularly important in header files, as these affect every translation unit that uses them.

    uint64_t carry /* only 0 or 1 */)


I dislike that comment style. Because the comment is almost, but not quite, at the end of line, it's very easy to miss the ) hiding there, and mis-parse.

If carry can only be 0 or 1, does it really make sense to pass as a 64-bit type? Certainly the bitwise arithmetic to create the carry-out is unlikely to create better code than plain logic && and || (any decent compiler can avoid unnecessary jumps because none of the operands have side-effects).

The test cases seem to have missed an important case in add_with_carry() (I know you said not to review that, but it's relevant for the subtract function):

#include <gtest/gtest.h>

TEST(add_with_carry, ci_causes_co)
{
uint64_t small = 0;
uint64_t big = ~small;
uint64_t result;
EXPECT_EQ(add_with_carry(result, small, big, 0), 0);
EXPECT_EQ(result, big);
EXPECT_EQ(add_with_carry(result, small, big, 1), 1);
EXPECT_EQ(result, 0);
}


The corresponding test of subtraction succeeds:

TEST(subtract_with_borrow, ci_causes_co)
{
uint64_t small = 0;
uint64_t big = ~small;
uint64_t result;
EXPECT_EQ(subtract_with_borrow(result, 0, 0, 0), 0);
EXPECT_EQ(result, 0);
EXPECT_EQ(subtract_with_borrow(result, 0, 0, 1), 1);
EXPECT_EQ(result, big);
}


So the two functions are not directly comparable. It's a shame you didn't include the tests for review - given that you've missed probably the most important boundary case, then the testing may well be deficient in other ways too.

To make the tests pass, I needed to make the logic of the two functions equivalent to each other:

static
auto subtract_with_borrow(uint64_t& result,
uint64_t left, uint64_t right,
bool borrow)
{
result = left - right - borrow;
return left < right || left == right && borrow;
}

static
auto add_with_carry(uint64_t& result,
uint64_t left, uint64_t right,
bool carry)
{
result = left + right + carry;
return left > ~right || left == ~right && carry;
}


Now that both tests pass, the corresponding assembly outputs look very similar to each other.

• I disagree about <cstdint>. I believe that [u]intN_t should've been fundamental types like int, and the fact that they are implemented as typedefs is a historical mistake. When considered like that, putting them into std doesn't make much sense. Jun 24 at 11:49
• You are correct about my add_with_carry being broken, of course. But I believe an implementation exactly symmetric with subtract_with_borrow would be result = left + right + carry; return result < left || result == left && carry; Jun 24 at 12:12
• You could do it that way, and change subtract_with_borrow to match. It's arguably better to not use result in computing the return value, though, as that allows more parallelism in a superscalar CPU. Jun 24 at 12:49
• I'm not convinced that optional types could, never mind should, have been fundamental! Jun 24 at 12:50