How to handle negative numbers: getting quotient and remainder without the '/', '%', and '*' operators in C

Question

This program works in handling positive integers, but not on negative integers. How can I fix this one? Thanks!

By the way, is my code good or not? Is there a better way on getting the quotient and remainder without using the '/', '%', and '*' operators?

#include <stdio.h>

int divide(int x, int y, int quotient);
int getRem(int x, int y, int quotient, int product, int count, 
int remainder);

int main()
{
        int dividend, divisor, quotient = 0, product = 0;
    int remainder, count = 0;

    scanf("%d %d", &dividend, &divisor);

    printf("\nQuotient: %d", divide(dividend, divisor, quotient));

    quotient = divide(dividend, divisor, quotient);

    printf("\nRemainder: %d", getRem(dividend, divisor, quotient, product, count, remainder));
}
int divide(int x, int y, int quotient)
{
        while (x > 0)
    {
        x -= y;
        quotient++;
    }
    if (x != 0)
        return quotient - 1;
    else
        return quotient;
}
int getRem(int x, int y, int quotient, int product, int count, int remainder)
{
    while (count != y)
    {
        product += quotient;
        count++;
        remainder = x - product;
        }
    return remainder;
}

Answer 1

This program works in handling positive integers, but not on negative integers. How can I fix this one?

When you call :

• divide(-10, 3) or divide(-10, -3) the while loop condition while(x > 0) will be false
• divide(10, -3) the while loop will be infinite loop because of the statement x -= y. (x) will be increase by the value of (y)

is my code good or not? Your code is need to be organized:

• in the main function you need to pass only the necessary parameters. in the divide function why you pass the quotient. the quotient will be calculated inside the function. so that you should edit the prototype to int divide(int x, int y);.

• the same thing with getRem function you should edit the prototype to int getRem(int x, int y);.

• in the main function you are calling the divide function twice to print the quotient and to save the quotient in the variable quotient. instead you should call the function only one time and reuse the returned value.

After the previous points your main and functions prototypes should be as follow:

#include <stdio.h>

int divide(int x, int y);
int getRem(int x, int y);

int main()
{
    int dividend, divisor, quotient = 0;

    scanf("%d %d", &dividend, &divisor);

    quotient = divide(dividend, divisor);

    printf("\nQuotient: %d", quotient);

    printf("\nRemainder: %d", getRem(dividend, divisor));
}

Now lets analyze the function divide. The first point, In math when multiplying or dividing, you actually do the operation on the sign as doing on the number. the following is the math rules for multiply or divide the sign.

• negative * positive -> negative
• positive * negative -> negative

• negative * negative -> positive

• negative / positive -> negative

• positive / negative -> negative
• negative / negative -> positive

The second point is the while loop. You should divide until (x) is less than (y).

As an example: suppose x = 7, y = 3 :

• after first loop x -> 4 and y -> 3
• after second loop x -> 1 and y -> 3 so that the condition should be while(x >= y)

so now you should first manipulate the sign division after that the numbers division. as follows.

int divide(int x, int y)
{
    int quotient = 0;
    //save the resulting sign in the sign variable
    int sign = 1;
    int temp = 0;
    /*   sign division  */
    // negative / positive -> negative
    if((x < 0) && (y >= 0)){
        sign = -1;
        temp = x;
        x -= temp;
        x -= temp;
    }// positive / negative -> negative
    else if((x >= 0) && (y < 0)){
        sign = -1;
        temp = y;
        y -= temp;
        y -= temp;
    }// negative / negative -> positive
    else if((x < 0) && (y < 0)){
        temp = x;
        x -= temp;
        x -= temp;

        temp = y;
        y -= temp;
        y -= temp;
    }
    while (x >= y)
    {
        x -= y;
        quotient++;
    }

    if(sign < 0){
        temp = quotient;
        quotient -= temp;
        quotient -= temp;
    }
        return quotient;
}

Lets go into the getRem function. The remainder(%) operation rules is as follows:

• negative % (negative or positive) -> negative
• positive % (negative or positive) -> positive

note: the result follows the sign of the first operand

As an Example:

• suppose x = -10 and y = 3, x / y = -3, to retrieve (x) multiply y and -3, so x = y * -3 = -9 the remainder is equal to -1
• suppose x = 10 and y = -3, x / y = -3',x = y * -3 = 9` the remainder is equal to 1

now apply the previous points on the getRem function to get the following result:

int getRem(int x, int y) 
{
    int temp, remSign = 1;
    if(x < 0){
        remSign = -1;
        temp = x;
        x -= temp;
        x -= temp;
    }

    if(y < 0){
        temp = y;
        y -= temp;
        y -= temp;
    }
    while (x >= y)
    {
        x -= y;
    }
    if(remSign < 0){
        x = -x;
    }
    return x;
}

You can to combine the two operation in one function using pointers for remainder as follows:

#include <stdio.h>

int divide(int x, int y,int * rem);
int getRem(int x, int y);

int main()
{
    int dividend, divisor, quotient = 0;
    int rem;
    scanf("%d %d", &dividend, &divisor);

    quotient = divide(dividend, divisor, &rem);
    printf("\nQuotient: %d", quotient);
    printf("\nRemainder: %d", rem);
}
int divide(int x, int y, int * rem)
{
    int quotient = 0;
    int sign = 1;
    int remSign = 1;
    int temp = 0;
    if((x < 0) && (y >= 0)){
        sign = -1;
        remSign = -1;
        temp = x;
        x -= temp;
        x -= temp;
    }
    else if((x >= 0) && (y < 0)){
        sign = -1;
        temp = y;
        y -= temp;
        y -= temp;
    }
    else if((x < 0) && (y < 0)){
        temp = x;
        x -= temp;
        x -= temp;

        temp = y;
        y -= temp;
        y -= temp;
    }
    while (x >= y)
    {
        x -= y;
        quotient++;
    }
    if(remSign < 0){
        *rem = -x;
    }else{
        *rem = x;
    }
    if(sign < 0){
        temp = quotient;
        quotient -= temp;
        quotient -= temp;
    }
        return quotient;
}

Answer 2

Is there a better way of getting the quotient and remainder without using the '/', '%', and '*' operators?

The majority of the time, I think, by far the best way of computing quotient and remainder is with the / and % operators. (It's their job, after all!)

If you need both quotient and remainder at the same time, there's also the div function, which does exactly that. (Its return value is a struct containing quot and rem members.) It's a bit cumbersome to use, but it might be more efficient if it means executing a single divide instruction (which tends to give you both quotient and remainder at the machine level anyway) instead of two. (Or, these days, with a modern optimizing compiler, I suspect it wouldn't make any difference anyway.)

But no matter how you do it, there's always a question when it comes to negative numbers. If the dividend or the divisor is negative, what sign(s) should the quotient and remainder be? There are basically two answers. (Actually, there are more than two, but these are the two I think about.)

• In Euclidean division, the remainder is always positive, and is therefore always in the range [0,divisor) (that is, between 0 and divisor-1).

• In many programming languages (including C), the remainder always has the sign of the dividend.

See the Wikipedia article on modulo operation for much, much more information on these and other alternatives.

If your programming language gives you the second definition (as C does), but you want a remainder that's never negative, one way to fix it is just to do a regular division, test whether the remainder is negative, and if it is, increment the remainder by the divisor and decrement the quotient by 1:

quotient = x / y;
remainder = x % y;
if(remainder < 0) {
    reminder += y;
    quotient--;
}

This works because of the formal definition of integer division with remainder:

div(x, y) → q, r such that y × q + r = x

If you subtract 1 from q and add y to r, you get the same result, and it's still x.

Here's a sample program demonstrating three different alternatives. I've encapsulated the little "adjust quotient for nonnegative remainder" algorithm as the function euclid(), which returns the same div_t type as div() does:

#include <stdio.h>
#include <stdlib.h>

div_t euclid(int, int);

int main()
{
    int x = -7, y = 3;
    printf("operators: q = %d, r = %d\n", x/y, x%y);
    div_t qr = div(x, y);
    printf("div: q = %d, r = %d\n", qr.quot, qr.rem);
    qr = euclid(x, y);
    printf("euclid: q = %d, r = %d\n", qr.quot, qr.rem);
}

div_t euclid(int x, int y)
{
    div_t qr = div(x, y);
    if(qr.rem < 0) {
        qr.quot--;
        qr.rem += y;
    }
    return qr;
}

To really explore this, you'll want to try things out for all four cases:

• positive dividend, positive divisor (the normal case, no ambiguity)
• negative dividend, positive divisor (the case I showed)
• positive dividend, negative divisor
• negative dividend, negative divisor

Answer 3

By the way, is my code good or not?

Well, there's room for improvements...

First of all - don't pass unnecessary variables to your function!

A function that shall divide x by y shall only take x and y as arguments. Whatever variables you need inside the function shall be defined inside the function.

So the first step is to change your divide function to be:

int divide(int x, int y)
{
    int quotient = 0;  // use a local variable
    while (x > 0)
    {
        x -= y;
        quotient++;
    }
    if (x != 0)
        return quotient - 1;
    else
        return quotient;
}

Another (minor) issue is the two return statements. With a simple change of the while statement that can be avoided.

int divide(int x, int y)
{
    int quotient = 0;  // use a local variable
    while (x >= y)     // notice this change
    {
        x -= y;
        quotient++;
    }
    return quotient;
}

Also notice that a call like divide(42, 0); will cause an infinite loop. So perhaps you should check for y being zero.

The algorithm can be improved - especially for large numbers - but I guess you want a simple approach so I stick to your basic algorithm.

... but not on negative integers. How can I fix this one?

A simple approach is to convert any negative input before entering the loop and maintain a counter to remember the number of negative numbers. Something like:

int divide(int x, int y)
{
  int quotient = 0;
  int negative = 0;
  if (x < 0)
  {
    x = -x;     // Make x positive
    ++negative;
  }
  if (y < 0)
  {
    y = -y;     // Make y positive
    ++negative;
  }
  while (x >= y)  // Both x and y are positive here
  {
    x -= y;
    quotient++;
  }
  return (negative == 1) ? -quotient : quotient;
}

int main(void)
{
  printf("%d\n", divide( 5, 2));
  printf("%d\n", divide( 5,-2));
  printf("%d\n", divide(-5, 2));
  printf("%d\n", divide(-5,-2));

  printf("%d\n", divide( 6, 2));
  printf("%d\n", divide( 6,-2));
  printf("%d\n", divide(-6, 2));
  printf("%d\n", divide(-6,-2));

  return 0;
}

Output:

2
-2
-2
2
3
-3
-3
3

You can apply the same kind of changes to the function getRem and I'll leave that part for you as an exercise...

However, notice that your current function uses quotient without any benefit. The function (only handling positive numbers) could simply be:

int getRem(int x, int y) // requires x >= 0 and y > 0
{
    while (x >= y)
    {
        x -= y;
    }
    return x;
}