Integer arithmetic is surprisingly difficult to get right. There are usually lots of weird corner cases and the temptation to use too-clever bit-twiddling tricks is high. Today I thought I’d give an example of how I approach solving integer arithmetic problems on those rare occasions when I have to. So let’s consider the problem of writing a C# method that divides two 32 bit integers such that the division rounds up if it is inexact.
Before creating a new kind of division, it is instructive to consider what the existing integer division operator does. Obviously it divides a dividend by a divisor and produces a quotient, but there are some corner cases. The most obvious corner case is when the divisor is zero. Less obvious is the case where the dividend is Int32.MinValue and the divisor is -1. The correct answer mathematically is one greater than Int32.MaxValue. And as I discussed in 2011, it’s not immediately clear whether -5 divided by 2 should have a quotient of -3 and a remainder of 1 or a quotient of -2 and a remainder of -1. Opinions vary.
The C# specification is mostly clear on all of these points. Summing up:
- Division by zero results in an exception.
- Division of
Int32.MinValueby-1either results inInt32.MinValueor an exception, at the discretion of the implementor. - If the divisor and dividend have the same sign then the result is zero or positive.
- If the divisor and dividend have opposite signs then the result is zero or negative.
- If the division is inexact then the quotient is rounded towards zero. That is, up if it is negative, and down if it is positive.
Now let’s use this as a model for our new method. That “implementation defined” point in there is a bit vexing, so let’s eliminate it. Our proposed method should have the following behaviour:
- Division by zero results in an exception.
- Division of
Int32.MinValueby-1results in an exception. - If the divisor and dividend have the same sign then the result is zero or positive.
- If the divisor and dividend have opposite signs then the result is zero or negative.
- If the division is inexact then the quotient is rounded up.
And now we have a specification from which we can write completely straightforward, boring code. Our implementation strategy will take advantage of the fact that the built-in operator does the heavy lifting; it already gives the desired result in the majority of cases, and only needs a small fixup in the few cases where it does not round up.
So when does regular division need to be fixed up? When the division is both inexact and rounded down. We can tell if the division was inexact if the remainder operator produces a non-zero result. But how can we tell if the division was rounded down?
We round towards zero, so the division was rounded down if the exact mathematical quotient was a positive fraction, and it was a positive fraction if the divisor and dividend were of the same sign. This is the point where people mess up. There is an easy way to determine if two numbers are of the same sign, and that’s to compare their signs. The moment you depart from that, you get into trouble. In particular, multiplying two 32 bit integers together and checking to see if the result is positive does not tell you that the two integers were of the same sign! Integer arithmetic overflows; if it throws an exception in a checked context then obviously you do not know whether the two numbers were of the same sign. If it overflows in an unchecked context then two positive multiplicands can produce a negative product. Don’t get cute; if you want to check if two things are the same then compare them for equality.
Enough chit-chat; let’s write some code.
public static int DivRoundUp(int dividend, int divisor)
{
if (divisor == 0 )
throw new DivideByZeroException();
if (divisor == -1 && dividend == Int32.MinValue)
throw new OverflowException();
int roundedTowardsZeroQuotient = dividend / divisor;
bool dividedEvenly = (dividend % divisor) == 0;
if (dividedEvenly)
return roundedTowardsZeroQuotient;
At this point we know that the divisor was not zero (because we would have thrown) and we know that the dividend was not zero (because there would have been no remainder). Therefore both are non-zero. Either they are of the same sign, or opposite signs. If they’re of opposite sign then rounding towards zero rounded up, so we’re done. If they’re of the same sign then rounding towards zero rounded down, so we must add one to the quotient.
We compare signs by comparing signs:
bool wasRoundedDown = ((divisor > 0) == (dividend > 0));
if (wasRoundedDown)
return roundedTowardsZeroQuotient + 1;
else
return roundedTowardsZeroQuotient;
}
Now, is this the shortest way to write this code? No. Is it the fastest? No. Is it the cleverest? Certainly not. But it is clear, logical, follows the structure of its specification closely, and therefore more likely to be correct than shorter, faster, cleverer code. This variation has fewer tokens, and is considerably more clever:
bool wasRoundedDown = (divisor ^ dividend) >= 0;
It also trades two comparisons for one xor and therefore might be a few nanoseconds faster; I don’t know. If this method turned out to be a bottleneck then you could experiment and find out. But I do know that the less clever version is a lot easier to read.
Next time on FAIC: I play Spot the Defect at the HUB.
Fabulous adventures in coding 
Two questions, one about coding good practice and the other about machine code generation for .net:
1) In the specification the “%” operator have a well defined behaviour (OverFlowException) when the dividend is int.MinValue and the divisor -1, same for the “/” in checked context, is it ok for you to leave for the operator to throw the exceptions?
2) When I use both “/” and “%” operators near each other with same operands the code generation will emit one or two division instructions?
1) Sure. Though that makes the code somewhat less clear.
2) That’s up to the implementation. Some hardware exposes a “compute both the quotient and the remainder at the same time” instruction. Whether any of the jitters take advantage of that if it is available, I do not know.
Regarding 2) I would not count on it, although I haven’t checked emitted assembly. I guess your best bet would be to call
System.Math.DivRem(int, int, out int)instead.OK, so maybe I’m stupid, but I’m completely missing the intentional pun.
The article linked to is about choosing the correct integer division algorithm in order to identify which corners in a maze the user can see around, hence, tricky corner cases HA HA HA I CRACK MYSELF UP.
If you read the whole series you’ll discover that both “round up” and “round down” integer division algorithms are subtly wrong.
aha… I didn’t read that far into the linked article (I figured if the title didn’t give it to me, it was a dead end).
I wa thinking it had to do with find corners in something that was “round”.
Me too, you are not alone 🙂
Going from ((divisor > 0) == (dividend > 0)) to (divisor ^ dividend) >= 0 is a bit tricky. It relies on the fact that both divisor and dividend cannot be 0. If divisor were 0, an exception would have been thrown. If dividend were 0, dividedEvenly would have been true, and the function would have returned already. Knowing that, ((divisor > 0) == (dividend > 0)) is equivalent to ((divisor >= 0) == (dividend >= 0)) or ((divisor < 0) == (dividend < 0)), which can then indeed be shortened to (divisor ^ dividend) >= 0. My personal preference goes to ((divisor < 0) == (dividend < 0)), for the simple reason that I have seen it enough in C for it to have become idiomatic: “use x < 0 to get the value of the sign bit”. Which is strictly not even true in C. In this case, of course, they all work just as well.
You can improve the trick:
return roundedTowardsZeroQuotient + 1 + ((divisor ^ dividend) >> 31);Good day, Mr. Lippert:
Nice to meet you, over the Internet. I’m the user Ken Kin from stackoverflow.com.
If I understand correctly, this is a discussion about semantic meaning through an example of integer arithmetic.
I supposed the “clever version” of comparision in which integer arithmetic, might presenting the thinking of 2’s complement.
I’m a Mandarin speaker, and used to write in Traditional Chinese. In Chinese(I think “-nese” was not good) language, we have “classical Chinese(文言文)” and “vernacular Chinese(白話文)”, the former is in a more simplified form some like poems, even be confused to a lot of people who speak Chinese.
But sometimes we might found “vernacular Chinese” been too verbose of like “Has anyone really been far as decided to use even go want to do look more like?” I were complained about doing so in English, because my English is poor, I construct a sentence with many words, and even not aware what were redundant.
Though I was used to write code in the way that you described as “clever code”, I would be on the same side of you with high-level languages. I think that the optimization should be done by the compiler.
In another example, with the “as” and “is” operators in c#, I wrote code like this before:
var that=it as ReturnType;
if(null!=that)
return that;
As time went on, I then write same the code in this way:
if(it is ReturnType)
return it as ReturnType;
You didn’t mention the first incorrect idea that popped through my head when reading the spec:
“If the division is inexact then the quotient is rounded towards zero. That is, up if it is negative, and down if it is positive.”
We just have to check the sign of the result! It’s rounded down if it’s positive!
But of course this strategy fails when it comes to a 0 quotient.
BTW I am not sure how MinValue / -1 == MinValue could make sense, although it’s allowed by the spec. Especially since the same spec also says that two operand with the same sign should give a zero or positive result.
I guess it’s because this is the hardware behavior, so it’s cheap?
It’s because MinValue / -1 = MaxValue + 1, and MaxValue + 1 gives you MinValue because of integer overflow.
And why is mathematically correct MinValue/-1 = MaxValue + 1?
Sorry if the question is obvious or is on some of the links and I missed it.
Because MinValue is -2147483648 and MaxValue is 2147483647.
Ok, sorry for that. Should have checked that, I was stupidly assuming the min value was positive
Thanksalotfor answering such a question
The term “rounded up” is unclear, since the term may either imply “rounded away from zero” or “rounded toward positive infinity”. Also, the normal approach I would use for this sort of math would be to, after checking that neither operand is zero, identify the four quadrant cases before attempting a division, and then adjust operands to avoid further conditional tests [e.g. when a and b are both greater than zero, a/b rounded up is 1+(a-1)/b, whether or not a divides b].
“The term “rounded up” is unclear, since the term may either imply “rounded away from zero” or “rounded toward positive infinity”.”
No, because “up” means “toward positive infinity.” “rounded away from zero” means “negative numbers toward negative infinity.”
To be fair people sometimes informally say round up when they mean round away from 0. however Eric clearly means round up as round towards infinity given the rest of the article.
On another note I’m always amazed by how many people on SO questions about rounding, think that round towards 0 is the only ‘correct’ way to round.
I’ve heard term “rounded down” used to describe “rounded toward zero”, and to describe “rounded toward negative infinity”. Neither usage is uncommon. Without examining the code, I would not have been certain of which meaning was intended by “rounded up”.
As for people thinking that rounding toward zero is the “correct” way, my personal philosophy would be that the “normal” operator should specify round-toward-negative-infinity when the divisor is positive, and Undefined Behavior in all other scenarios [probably with an option to trap in debug builds]. That would allow power-of-two divisions to be replaced with shifts, and modulus operations with bit-AND. Further, even when the language specifies how the operators will behave with negative numbers, I would regard code that performs negative-number division in terms of positive-number division as more readable than code which “adjusts” the results of negative-number division.
Hey Eric,
I remember reading your answer to this question on StackOverflow a while back. It was a great answer to an common question.
I actually found the answer posted by “jerryjvl” to be far more interesting mostly because of your comments on that answer. The answer was essentially a series guesses that eventually became roughly the same as your answer after enough tries. In the comments section, you gave examples of corner cases for which some of the guesses gave incorrect results.
Having read that SO answer really helped me appreciate why you kept stressing “check that two things are the same by comparing for equality.”
Please keep blogging about topics from SO questions. There are a lot of interesting ones left!
Indeed, I have a long list. That thing is a gold mine for blog topics. And yes, it was funny how many wrong answers were posted.
– Division of Int32.MinValue by -1 either results in Int32.MinValue or an exception, at the discretion of the implementor.
– If the divisor and dividend have the same sign then the result is zero or positive.
Those two rules seem to contradict each other. Do you why that was left up to implementation? What is the perceived benefit to having Int32.MinValue / -1 = Int32.MinValue? It just seems like a great source of bugs, in my opinion.
Many of the processors on which C# code will be run have an “integer divide” instruction which can accept two arbitrary integers and return results which are consistent with “round toward zero” arithmetic for all scenarios other than -int.MinValue/-1. It would be wasteful for a compiler to generate code to ensure that an exception occurs in that scenario, especially given that in many programs it cannot actually occur.
Indeed, I suspect the decision to specify round-toward-zero semantics was predicated not on semantic superiority, but rather on the facts that (1) on any processor that includes a “signed divide” instruction, specifying any semantics other than the natural semantics of that instruction will require the generation of extra code for every division operations which, from the compiler’s perspective, could involve negative operands, **even if the operands would in practice never actually be negative**; (2) hardware which implements round-toward-zero is more common than hardware which does other things, so it makes sense to minimize the burden on the former hardware. That having been said, if one were designing a language from scratch, it might make sense to have two sets of division operators, one of which would implement Euclidian semantics despite the cost, and one of which would only be specified to work for positive numbers and–at least in debug builds–would trap negative values.
re:
“it’s not immediately clear whether -5 divided by 2 should have a quotient of -3 and a remainder of 1 or a quotient of -2 and a remainder of -1. Opinions vary.”
I have to fight this out with the Integer Division and Modulus operators every few years. In 30 years I have always wanted the smooth behaviour instead of the (default) un-smooth behaviour. For the next time a C-like language is being developed, can we get this one right finally? K&R did a ton of good work, but made 2 careless errors that I know of. The other has been fixed, it would be nice to see this one fixed (somewhere) before I retire. 😉
For what it’s worth, it’s my opinion that function defaults should follow this rule:
1) Choose smoth ahead of of un-smooth; and
2) Choose continuous ahead of discontinuous.
To flog a dead horse:
3) Default behaviour should not invalidate the Distributive Law just because values creep below 0.
4) The integers should remain a Ring even when negative values occur.
5) The unary-minus operator should remain identical to the binary-minus operator for negative integers as well as positive ones.
Pingback: Five-dollar words for programmers: elision | Fabulous adventures in coding
Pingback: ensure that division of integers is always rounded up | Coding and Programing
Pingback: How can we pledge that a multiplication of integers is always lifeless up? - Zunker Gyan
Pingback: How to: How can I ensure that a division of integers is always rounded up? | SevenNet
Pingback: Fixed How can I ensure that a division of integers is always rounded up? #dev #it #asnwer | Good Answer
Pingback: Resolved: How can I ensure that a division of integers is always rounded up? #answer #programming #computers | IT Info
Pingback: Long division, part two | Fabulous adventures in coding
Pingback: How can I ensure that a division of integers is always rounded up? | ASK AND ANSWER
Pingback: How can I ensure that a division of integers is always rounded up? – Knowleage Exchange
Pingback: How can I ensure that a division of integers is always rounded up? - CodeDay
Pingback: Ten Emerging Addiction treatment Developments To watch In 2023 — it-labx.ru
Pingback: [C#] How can I ensure that a division of integers is always rounded up? - Pixorix