cbit-manipulationundefinedbitwise-operatorsdivision

Bitwise division in C : Programme seems to work for other numbers but when the divisor is 0 it returns 11 for no apparent reason


I am trying to solve the problem posed in this question which asks that division of two numbers be performed in a bitwise manner. So, I wrote the following functions.

sum() adds two numbers.
larger() returns the bigger of the two numbers.
difference() subtracts the smaller from the bigger of two numbers.
length() calculates how many bits a number has.
quotient() calculates the quotient of two numbers.
product() calculates the product of two numbers.
_remainder()() calculates the remainder of two numbers.
main() takes inputs and prints outputs.\

My code looked like this -

#include <stdio.h>

unsigned int sum (unsigned int x, unsigned int y)
{
    unsigned int sum = x ^ y;
    for (unsigned int temp = sum, carry = (x & y) << 1; carry != 0; sum ^= carry, carry = (temp & carry) << 1) {}
    return sum;
}

unsigned int larger (unsigned int x, unsigned int y)
{
    unsigned int big = x & ~y, small = ~x & y;
    for (;; big >>= 1, small >>= 1)
    {
        if (big == 0) { return y; }
        if (small == 0) { return x; }
    }
}

unsigned int difference (unsigned int x, unsigned int y)
{
    unsigned int big = larger (x, y), small;
    if (big == x) { small = y; } else { small = x; }
    return sum (big, sum (~small, 1));
}

unsigned int length (unsigned int x)
{
    unsigned int length = 0;
    for (unsigned int temp = x; temp != 0; temp >>= 1, length = sum (length, 1)) {}
    return length;
}

unsigned int quotient (unsigned int x, unsigned int y)
{
    unsigned int quotient = 0;
    for (unsigned int _remainder = x, lenx = length(x), leny = length(y), temp = x >> (difference (lenx, leny)), big = larger (temp, y); larger (_remainder, y) == _remainder; lenx = length(_remainder), temp = _remainder >> (difference (lenx, leny)), big = larger (temp, y))
    {
        if (big == temp)
        {
            _remainder = difference (_remainder, (y << (difference (lenx, leny))));
            quotient |= (1 << (difference (lenx, leny)));
        }
        else
        {
            _remainder = difference (_remainder, (y << (difference (lenx, sum (leny, 1)))));
            quotient |= (1 << (difference (lenx, sum (leny, 1))));
        }
    }
    return quotient;
}

unsigned int product (unsigned int x, unsigned int y)
{
    unsigned int product = 0;
    for (unsigned int shift = x, carry = y; carry != 0; shift <<= 1, carry >>= 1)
    {
        if (carry & 1) { product = sum (product, shift); }
    }
    return product;
}

unsigned int _remainder (unsigned int x, unsigned int y)
{
    return difference (x, product (y, quotient (x, y)));
}

int main (void)
{
    for (;;)
    {
        unsigned int x, y;
        printf ("Give me a natural number x = ");
        if (scanf ("%d", &x) != 1) { printf ("error\n"); break; }
        printf("Give me another natural number y = ");
        if (scanf ("%d", &y) != 1) { printf ("error\n"); break; }
        printf ("\n");
        printf ("The quotient x/y = ");
        printf ("%u", quotient (x, y));
        printf ("\n");
        printf ("The remainder x%y = ");
        printf ("%u", _remainder (x, y));
        printf ("\n\n\n");
    }
    return 1;
}

When run the code seemed to work. When the divisor is 0 it hangs, which is what it is supposed to do. But, I wanted it to print Undefined!! when the divisor is 0. So, I introduced an if-else statement in the function quotient() and _remainder() in order to achieve this behaviour manually. My code then looked like this -

#include <stdio.h>

unsigned int sum (unsigned int x, unsigned int y)
{
    unsigned int sum = x ^ y;
    for (unsigned int temp = sum, carry = (x & y) << 1; carry != 0; sum ^= carry, carry = (temp & carry) << 1) {}
    return sum;
}

unsigned int larger (unsigned int x, unsigned int y)
{
    unsigned int big = x & ~y, small = ~x & y;
    for (;; big >>= 1, small >>= 1)
    {
        if (big == 0) { return y; }
        if (small == 0) { return x; }
    }
}

unsigned int difference (unsigned int x, unsigned int y)
{
    unsigned int big = larger (x, y), small;
    if (big == x) { small = y; } else { small = x; }
    return sum (big, sum (~small, 1));
}

unsigned int length (unsigned int x)
{
    unsigned int length = 0;
    for (unsigned int temp = x; temp != 0; temp >>= 1, length = sum (length, 1)) {}
    return length;
}

unsigned int quotient (unsigned int x, unsigned int y)
{
    if (y != 0)
    {
        unsigned int quotient = 0;
        for (unsigned int _remainder = x, lenx = length(x), leny = length(y), temp = x >> (difference (lenx, leny)), big = larger (temp, y); larger (_remainder, y) == _remainder; lenx = length(_remainder), temp = _remainder >> (difference (lenx, leny)), big = larger (temp, y))
        {
            if (big == temp)
            {
                _remainder = difference (_remainder, (y << (difference (lenx, leny))));
                quotient |= (1 << (difference (lenx, leny)));
            }
            else
            {
                _remainder = difference (_remainder, (y << (difference (lenx, sum (leny, 1)))));
                quotient |= (1 << (difference (lenx, sum (leny, 1))));
            }
        }
        return quotient;
    }
    else { printf ("Undefined!!"); }
}

unsigned int product (unsigned int x, unsigned int y)
{
    unsigned int product = 0;
    for (unsigned int shift = x, carry = y; carry != 0; shift <<= 1, carry >>= 1)
    {
        if (carry & 1) { product = sum (product, shift); }
    }
    return product;
}

unsigned int _remainder (unsigned int x, unsigned int y)
{
    if (y != 0) { return difference (x, product (y, quotient (x, y))); }
    else { printf ("Undefined!!"); }
}

int main (void)
{
    for (;;)
    {
        unsigned int x, y;
        printf ("Give me a natural number x = ");
        if (scanf ("%d", &x) != 1) { printf ("error\n"); break; }
        printf("Give me another natural number y = ");
        if (scanf ("%d", &y) != 1) { printf ("error\n"); break; }
        printf ("\n");
        printf ("The quotient x/y = ");
        printf ("%u", quotient (x, y));
        printf ("\n");
        printf ("The remainder x%y = ");
        printf ("%u", _remainder (x, y));
        printf ("\n\n\n");
    }
    return 1;
}

It almost produces the behaviour I expected, it prints Undefined!! when the divisor is 0, but the functions quotient() and _remainder() now return 11 for no apparent reason. The if-else statements in functions quotient() and _remainder() explicitly tells it to print Undefined!! and break out of the function without returning anything in case the divisor is 0. Then why are the functions returning 11?


Solution

  • The if-else statements in functions quotient() and _remainder() explicitly tells it to print Undefined!! and break out of the function without returning anything in case the divisor is 0.

    There is no C statement to “break out of the function” except for special functions like longjmp, exit, and abort. Your if-else construction lets program control flow to the end of the function, not break. When program control reaches the end of the function, the function returns.

    When a function is declared with unsigned int quotient(…), there is no way to tell the calling routine nothing is being returned. In the calling routine, the printf ("%u", quotient (x, y)); continues as normal, so it attempts to print the value returned by the function.

    When you let a function with a non-void type return in this way and the calling routine attempts to use the return value, the behavior is not defined by the standard. One common result of this is that the program prints whatever value happens to be in the processor register where the return value would have been stored. That register may contain some value that was previously used in the program for another purpose.

    If you want your program to sometimes print a number for the quotient or the remainder and sometimes not, then you must arrange code in the main routine to decide whether or not to print a number.