Catch and compute overflow during multiplication of two large integers

by

1. Detecting the overflow:

x = a * b;
if (a != 0 && x / a != b) {
    // overflow handling
}

Edit: Fixed division by 0 (thanks Mark!)

2. Computing the carry is quite involved. One approach is to split both operands into half-words, then apply long multiplication to the half-words:

uint64_t hi(uint64_t x) {
    return x >> 32;
}

uint64_t lo(uint64_t x) {
    return ((1ULL << 32) - 1) & x;
}

void multiply(uint64_t a, uint64_t b) {
    // actually uint32_t would do, but the casting is annoying
    uint64_t s0, s1, s2, s3; 
    
    uint64_t x = lo(a) * lo(b);
    s0 = lo(x);
    
    x = hi(a) * lo(b) + hi(x);
    s1 = lo(x);
    s2 = hi(x);
    
    x = s1 + lo(a) * hi(b);
    s1 = lo(x);
    
    x = s2 + hi(a) * hi(b) + hi(x);
    s2 = lo(x);
    s3 = hi(x);
    
    uint64_t result = s1 << 32 | s0;
    uint64_t carry = s3 << 32 | s2;
}

To see that none of the partial sums themselves can overflow, we consider the worst case:

        x = s2 + hi(a) * hi(b) + hi(x)

Let B = 1 << 32. We then have

            x <= (B - 1) + (B - 1)(B - 1) + (B - 1)
              <= B*B - 1
               < B*B

I believe this will work – at least it handles Sjlver’s test case. Aside from that, it is untested (and might not even compile, as I don’t have a C++ compiler at hand anymore).

More Related Contents:

  1. How can I multiply and divide using only bit shifting and adding?
  2. Extracting bits with a single multiplication
  3. SIMD signed with unsigned multiplication for 64-bit * 64-bit to 128-bit
  4. Question about C behaviour for unsigned integer underflow
  5. Are the shift operators () arithmetic or logical in C?
  6. Find most significant bit (left-most) that is set in a bit array
  7. Fast computing of log2 for 64-bit integers
  8. How to convert integer to string in C? [duplicate]
  9. Bitfield manipulation in C
  10. Efficient unsigned-to-signed cast avoiding implementation-defined behavior
  11. Wrap around explanation for signed and unsigned variables in C?
  12. Finding the length of an integer in C
  13. What does -fwrapv do?
  14. C integer overflow
  15. Bitshift and integer promotion?
  16. Bit twiddling: which bit is set?
  17. How can I detect integer overflow on 32 bits int?
  18. How to define and work with an array of bits in C?
  19. Implementing Logical Right Shift in C
  20. How do I get bit-by-bit data from an integer value in C?
  21. Algorithm to generate bit mask
  22. How does this bitwise operation check for a power of 2?
  23. Check if a number is non zero using bitwise operators in C
  24. How would you set a variable to the largest number possible in C?
  25. Decimal to Binary
  26. C Programming – XOR Bitwise Operation
  27. What’s the difference between “int” and “int_fast16_t”?
  28. Bitwise shifting array of char’s
  29. How to implement Bitcount using only Bitwise operators?
  30. Can I compare int with size_t directly in C?

Leave a Comment