Using div with unsigned integers

Question

The C++ standard provides div(int, int), but not udiv(unsigned int, unsigned int).

If I naively used unsigned ints in this function, I can see that this would yield the wrong result for integers greater than 2^31 - 1 in the numerator. For example (with 4-bit nibbles):

The largest 4-bit nibble is 15, 1111 in binary. As a signed nibble, this would represent -1. Dividing 15 by 2 yields 7, or 0111, but dividing -1 by 2 yields 0: 0000.

Is there a straightforward way to adapt div to unsigned integers, or am I better off writing my own udiv, or avoiding the use of div and div-like functions altogether?

Edit/Note: In my case, I'm using unsigned long long ints, so using lldiv doesn't solve the problem.

Can you use C++11? There's an overload for `long long`, which is at least 64 bits. And pick one language. — juanchopanza, Aug 28 '15 at 21:51
I'm actually using C++11 to divide a uint64_t. I should edit my question to indicate that I'm interested in adapting lldiv. — castle-bravo, Aug 28 '15 at 21:52
That doesn't work if the `unsigned long long` is greater than 2^63 - 1. — castle-bravo, Aug 28 '15 at 21:54
a detail here: -1/2 is -.5 and when using an integer divide operation, fractions are always dropped. So the result is the expected 0. — user3629249, Aug 28 '15 at 23:58

score 16 · Accepted Answer · edited May 23 '17 at 11:51

Back in the day, the result of / and % were not uniquely defined by C and div() was born. Now quotient from / is truncated towards 0.

unsigned math did not have this issue and so a lesser need for udiv().

Now many compilers recognize nearby a/b and a%b calculations and optimize quite well, reducing the need for even div(). Suggest just performing both calculations and let the compiler optimize it.

[Edit]
Detail: Prior to C99, division may truncate toward 0, toward INT_MIN or (maybe could round to nearest - I'll look into that). In any case % is the remainder after the division. div() was specified to only do one: divide with truncate toward 0. With C99, both div() and / perform a division with the quotient truncated toward 0.

See
What is purpose of the div() library function?
What is the behavior of integer division?

"integer division truncates fractional results toward 0." Nothing else needs to be said — user3629249, Aug 29 '15 at 00:03

score 0 · Answer 2 · answered Aug 28 '15 at 21:53

0

Assuming you have an integer of n bytes, you can stocke k=2^n numbers, so if you have a negative number, getting its value as an unsigned would simply as adding k to it.

So what you could do is, test if the number is negatif, add k/q to the result.

However you could simply use the division operator /

answered Aug 28 '15 at 21:53

x4rkz

513
4
19

That will work for other than 2s complement representation? And for 2s complement, what about `INT_MIN`, etc.? – too honest for this site Aug 28 '15 at 22:18
1

this answer is not indicating why a integer divide where the divisor is greater than the numerator will always result in 0. – user3629249 Aug 29 '15 at 00:01

Using div with unsigned integers

2 Answers2