We are running a survey to help us improve the experience for all of our members. If you see the survey appear, please take the time to tell us about your experience if you can.
Hello to everyone.
When I have to calculate the average of two integer numbers, first i have to add them. Sometimes an overflow occurs. One technique maybe to compare the result to one of the numbers, if result is lower, an overflow is recognized.
Is this good style or better use Assembler?
How about something like that:
signed int Number1; signed int Number2; // Possibly CPU intensive, but quite accurate // even with odd numbers signed int AverageMethod1 = (signed int) ((long signed int)Number1 + (long signed int)Number2) / 2); // Faster but could be a couple of bits off // with odd numbers signed int AverageMethod2 = Number1 / 2 + Number2 / 2;
$0.02
Depends on your goal. Assembler can be fast, but at the expense of code readability and portability. In C, you can use different approaches. If your compiler supports a 64-bit long long type, you can use it to calculate the sum without the risk of overflow. If a 64-bit integer is not an option, you can use all kinds of tricks, like dividing by 2 prior to addition:
int average(int a, int b) { return a/2+b/2; /* instead of (a+b)/2 */ }
This way you will lose 1 bit of precision in the result. If this cannot be tolerated, you can you can adjust the result to restore precision:
int average(int a, int b) { return a/2+b/2+((((a+b)/2)<<31)>>31); }
I'm not sure about the last bit, you'd have to check the math. But you get the idea. Regards, - mike
In Assembly, the Carry flag signals if there was an overflow during an addition. There is no need to do any comparison.
Now, if you were to do the same in C, then yes, you would need to compare a number and the result.
"One technique maybe to compare the result to one of the numbers, if result is lower, an overflow is recognized."
Bad style for C.
According to the C Standard, integer overflow can invoke undefined behavior, regarding which, the Standard has a note:
"Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message)."
From the Standard's perspective, having monkeys fly out your nose would be allowed too.
It is commendable that you are trying to work through the issue of integer overflow. The problem is that your implementation can cause overflow. Once you have caused an overflow, you have undefined behavior. If you want to deal with the issue of integer overflow in a rigorous way, you can't expect to detect it after the fact, you must avoid overflow before causing undefined behavior. This typically involves using wider types as has been suggested, or checking whether one operand is less than the integer distance between the other operand and INT_MAX (or INT_MIN), or converting to unsigned arithmetic and examining the result.
I'd suggest searching Google Groups' Usenet archive for "avoiding integer overflow". This will bring up some relevant comp.lang.c(.moderated) discussions amongst folks smarter than I and give you a better idea what I'm talking about.
Hello to everyone, thanks for reply. Here's my Assembler solution, but i'am not sure it will deliver a correct result under all circumstances!
//********************************************************************* // Computing the average of signed/unsigned numbers in ARM Assembler //********************************************************************* AREA ?C?bla, CODE, READONLY, ALIGN=2 PUBLIC my_average?A my_average?A PROC CODE32 ADDS R0,R0,R1 ;add and alter condition code MOVVS R0,R0,RRX ;if sign has moved to C rotate through Carry MOVVC R0,R0,ASR #1 ;if sign not changed do arithmetic shift bx lr ; return R0 ENDP END //*********************************************************************
the KISS solution avarage = (a/2) + (b/2);
Erik
But the KISS solution yields:
"average of 5 and 7 = 5"
which is not the best integer answer. It all depends on the accuracy that is needed. That said, if being off by one bit every now and then is okay, then it is certainly the fastest solution.
Steph-
The slightly less simple solution fixes that:
average = (a/2) + (b/2) + (a%2 + b%2) / 2;
Here's the corrected version, divided into average for signed / unsigned numbers.
//********************************************************************* // Computing the average of Signed numbers in ARM Assembler //********************************************************************* AREA ?C?bla, CODE, READONLY, ALIGN=2 PUBLIC my_signed_average?A my_signed_average?A PROC CODE32 ADDS R0,R0,R1 ;add and alter condition code MOVVS R0,R0,RRX ;if sign has moved to C rotate through Carry MOVVC R0,R0,ASR #1 ;if sign not changed do arithmetic shift bx lr ;return R0 ENDP //********************************************************************* // Computing the average of Unsigned numbers in ARM Assembler //********************************************************************* PUBLIC my_unsigned_average?A my_unsigned_average?A PROC CODE32 ADDS R0,R0,R1 ;add and alter condition code MOV R0,R0,RRX ;rotate through Carry bx lr ;return R0 ENDP END //*********************************************************************