CODEWITHSUNDEEP
cinteger-overflow
user3393266
user3393266

Reputation: 59

Limit bit position of two variables before arithmetic to prevent integer overflow

I'm trying to limit arithmetic operations before they are executed to the result of at most 32 bit integers, specifically for addition.

This loop will find the bit position:

 size_t highestOneBitPosition(uint32_t a) {
     size_t bits=0;
     while (a!=0) {
         ++bits;
         a>>=1;
     };
     return bits;
 }

This function effectively limits multiplication:

 bool multiplication_is_safe(uint32_t a, uint32_t b) {
     size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
     return (a_bits+b_bits<=32);
 }

However, I'm unsure how to do this with addition. Something like this:

bool addition_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
return (a_bits<32 && b_bits<32);
}

However, this will not limit the integer to 32bit (or 0x7FFFFFFF for signed). It will make sure each operand has has that many bit positions.

Mathematically, if you add two numbers, you have at most a carry of 1 into the place beyond the longest. So if you add a 4 digit number to a 3 digit number (or anything 4 digits or less), you have at most a 5 digit number. Except, when you have two with the same, you can end up with more (99 * 99 = 9801) so then it would be the same concept as in multiplication (a_bits+b_bits <=32)

What I would have to do is determine the longest operand, then add 1 and make sure that it's not exceeding 32 bit positions. I am entirely unsure how to do this with a function. My question is how can I modify addition_is_safe(uint32_t a, uint32_t b) to limit the result to <=32 as it is in multiplication_is_safe. I definitely want to utilize the HighestOneBit Position with this.

Upvotes: 0

Views: 192

Answers (3)

Armali
Armali

Reputation: 19395

Mathematically, if you add two numbers, you have at most a carry of 1 into the place beyond the longest.

That's absolutely correct (for unsigned binary numbers) without exception; you just got lost in your further consideration. So, the addition_is_safe condition based on the summands' numbers of bits is: the highest number of bits of the summands has to be smaller than the available number of bits.

bool addition_is_safe(uint32_t a, uint32_t b)
{
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits<b_bits?b_bits:a_bits)<32;
}

Surely you are aware that a false return from that function doesn't always mean overflow would occur, but a true return means overflow cannot occur.

Upvotes: 0

JS1
JS1

Reputation: 4767

First of all, I don't even think that this function is correct:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
     size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
     return (a_bits+b_bits<=32);
}

It does return false when the multiply will overflow, but it also returns false when the multiply doesn't overflow. For example, given a = 0x10000 and b = 0x8000, this function returns false even though the result of a*b is 0x80000000 which fits in 32 bits. But if you change a and b to 0x1ffff and 0xffff (which have the same "highest one bit positions") then the multiply actually does overflow. But you couldn't tell by just using the highest bit position. You would need to look at more than just the top bit to figure out whether the multiplication will overflow. In fact, you would need to do part or all of the actual multiplication to figure out the right answer.

Similarly, you could construct a function addition_is_safe that detects "possible overflows" (both in the positive and negative direction) using bit positions. But you can't detect "actual overflow" unless you do part or all of the actual addition.

I believe that in the worst case, you will be forced to do the full multiplication or addition, so I'm not sure you will be saving anything by not letting the machine just do the full multiplication/addition for you.

Upvotes: 0

Andras
Andras

Reputation: 3055

you can check for overflow from adding two positive integers with (a + b) < a || (a + b) < b

overflow will either make the value negative (for signed integers), or will leave a smaller positive mode 32 remainder (for unsigned)

a positive added to a negative will never overflow

two negatives should be similar to two positives

Upvotes: -1

Related Questions