1. Write a C program called div.c that implements division on two unsigned integ

Question

1. Write a C program called div.c that implements division on two unsigned integers.

1. Name your executable div.out

2. You cannot use division in your solution

3. Arguments should be accepted from the command line

1. The first argument is the dividend

2. The second argument is divisor

4. Your program should display the quotient and remainder after doing the division

5. Your program must complete in O(1) (constant) time

1. This is possible because an integer is 32 bits long and so the loop that does the division

should not take longer than 32 iterations.

2. Because of this restriction the following solution is not acceptable as it does not meet

the O requirements

void bad_div(unsigned int dividend,

unsigned int divisor,

unsigned int* quotient,

unsigned int *remainder){

*quotient = 0;

while(dividend >= divisor){

(*quotient)++;

dividend -= divisor;

}

*remainder = dividend;

}

3. In order to meet the O requirements you will have to division in base 2 as you would by

hand. See these 2 articles for some examples: Dr. Math and Exploring Binary

1. Hint: use bitwise operators

2. The one step that they leave out and one that you normally skip when doing division

by hand is checking to see how many times the divisor goes into the dividend for the

numbers that contain fewer digits than the divisor.

1. For example: 30 / 15

2. First we should check how many times does 15 go into 3. The answer is 0.

3. Then we check how many times does 15 go into 30, which is 2.

4. So our answer would be 02 R 0

4. Examples:

1. ./div.out 10 5

10 / 5 = 2 R 0

2. ./div.out 100 17

100 / 17 = 5 R 15

Explanation / Answer

//Division using bitwise shift

#include <stdio.h>

int division(int dividend, int divisor, int origdiv, int * remainder)
{
    int quotient = 1;

    if (dividend == divisor)
    {
        *remainder = 0;
        return 1;
    }

    else if (dividend < divisor)
    {
        *remainder = dividend;
        return 0;
    }

    while (divisor <= dividend)
    {
        divisor = divisor << 1;
        quotient = quotient << 1;
    }

    if (dividend < divisor)
    {
        divisor >>= 1;
        quotient >>= 1;
    }

    quotient = quotient + division(dividend - divisor, origdiv, origdiv, remainder);

    return quotient;
}

int main()
{
    int dividend;
    int divisor;
    int rem = 0;

    printf (" Enter the Dividend: ");
    scanf("%d", &dividend);
    printf(" Enter the Divisor: ");
    scanf("%d", &divisor);

    printf("Quotient : %d ", division(dividend, divisor, divisor, &rem));
    printf("Remainder: %d ", rem);

    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.