Velocity Reviews > mod operator for signed integers

# mod operator for signed integers

Tim Rentsch
Guest
Posts: n/a

 04-10-2011
"dr.oktopus" <(E-Mail Removed)> writes:

> Ok, today I seems to be a little dumb.
> What I have to do is to make mod operator (m % n) work even
> if m is a negative number.
>
> This is what I mean:
>
> given n = 5
>
> 7 became 2
> 6 .. 1
> 5 .. 0
> 4 .. 4
> 3 .. 3
> 2 .. 2
> 1 .. 1
> 0 .. 0
> -1 .. 4
> -2 .. 3
> -3 .. 2
> -4 .. 1
> -5 .. 0
> -6 .. 4
> -7 .. 3
>
> I think that, for a operation like m % n, it could be:
>
> unsigned my_mod (int m, unsigned n)
> {
> unsigned um;
>
> if (m < 0) {
> um = -m;
> return n - um % n;
> }
> return m % n;
> }
>
> but, if m is INT_MIN, for example, its two complement (um)
> is 0, right? So, my_mod returns n (that is wrong).
>
> What's the right (and smart) way?

This statement

return m < 0 ? n-1 - -(m+1)%n : m%n;

gives correct results for all values of m and
all values of n with n>0.

Exercise: prove the expression for the m<0 case
works (and does not have undefined behavior).
(Hint: proving it works can be done in about 5 lines.)

Tim Rentsch
Guest
Posts: n/a

 04-10-2011
Eric Sosman <(E-Mail Removed)> writes:

> On 4/9/2011 10:53 AM, dr.oktopus wrote:
>> Ok, today I seems to be a little dumb.
>> What I have to do is to make mod operator (m % n) work even
>> if m is a negative number.
>>
>> This is what I mean:
>>
>> given n = 5
>>
>> 7 became 2
>> 6 .. 1
>> 5 .. 0
>> 4 .. 4
>> 3 .. 3
>> 2 .. 2
>> 1 .. 1
>> 0 .. 0
>> -1 .. 4
>> -2 .. 3
>> -3 .. 2
>> -4 .. 1
>> -5 .. 0
>> -6 .. 4
>> -7 .. 3
>>
>> I think that, for a operation like m % n, it could be:
>>
>> unsigned my_mod (int m, unsigned n)
>> {
>> unsigned um;
>>
>> if (m< 0) {
>> um = -m;
>> return n - um % n;
>> }
>> return m % n;
>> }
>>
>> but, if m is INT_MIN, for example, its two complement (um)
>> is 0, right? So, my_mod returns n (that is wrong).

>
> If `m' is INT_MIN, `-m' is either INT_MAX (on some very rare
> machines) or undefined (on most). The commonest "undefined" outcome
> is -INT_MIN -> INT_MIN, still negative.
>
>> What's the right (and smart) way?

>
> I don't know if this is "the" right or smart way, but:
>
> unsigned my_mod(int m, unsigned n) {
> if (m < 0) {
> unsigned um;
> m += (int)n; /* now m > INT_MIN */
> um = -m;
> return n - um % n;
> }
> return m % n;
> }

Not quite right. Consider m == -n, for example.

Eric Sosman
Guest
Posts: n/a

 04-10-2011
On 4/10/2011 4:27 AM, Tim Rentsch wrote:
> Eric Sosman<(E-Mail Removed)> writes:
>
>> On 4/9/2011 10:53 AM, dr.oktopus wrote:
>>> [...]
>>> What's the right (and smart) way?

>>
>> I don't know if this is "the" right or smart way, but:
>>
>> unsigned my_mod(int m, unsigned n) {
>> if (m< 0) {
>> unsigned um;
>> m += (int)n; /* now m> INT_MIN */
>> um = -m;
>> return n - um % n;
>> }
>> return m % n;
>> }

>
> Not quite right. Consider m == -n, for example.

Good catch; thanks. (That's what I get for considering only
the question asked and not thinking about the rest of the code...)

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d