2

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?

Improve this question
16
  • 2
    Have you stepped through the code line by line in a debugger, while monitoring of variables and their values? Commented Sep 14 at 11:42
  • 2
    Because your quotient() and remainder() functions don't (explicitly) return anything if y == 0, effectively returning garbage. Commented Sep 14 at 11:44
  • 1
    Yes, it's garbage (or more accurately, undefined) if the divisor is 0, since your code always takes the same path. 11 is as good a garbage number than anything else. Don't you get compiler warnings? Commented Sep 14 at 12:19
  • 1
    Any function defined with a return value (unsigned int in this case) must always return a value. You can not sometimes not return a value, because then it would return garbage. Your compiler should warn you about not returning a value. In C++ you could throw an exception, but C doesn't support exceptions. Commented Sep 14 at 12:23
  • 1
    @uran42 Your functions shouldn't call printf() in the first place. They should return a special value to indicated that the result is undefined. Your main() should check for this special value, using an if-else, and print 'Undefined' instead of the special value. Commented Sep 14 at 12:33

2 Answers 2

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

You say.

...and break out of the function without returning anything

(italic quotation is mine) You cannot break out of a function that is expected to return something without returning actually something, and more important if you plan and code to use that return value. The statement you write is U.B. (Undefined Behavior) basically because you end a function that should return an int without calling return some_integer_value;. The problem is that you are interpreting that not using return will make the function to return nothing, and that's simply a misinterpretation of the language rules. What should you expect the value to be? The function you call appears in an expression that will use the value returned, so what should the program do when you decide not to return anything? The absence of a return statement is normally issued as a warning message at compilation time, but warning messages can be ignored (as you probably have done) and you will get finally an executable, but erroneous program (this is done on purpose, for legacy reasons, as not always there was a void type to allow functions to return nothing, so they were declared ---implicitly--- int and you have to care yourself never using the returned value of such a function. Now this has been forgotten by many, and never known by others)

The way function call works is that the compiler, previous to the call to the function, must reserve resources to allow the function to return a value. This is done normally in the space reserved for temporary expression values (as the function call itself can be only part of the total expression calculations that have to be done) once the function is called, and after all housekeeping is done after the function call, the resources allocated before the call should hold the value (intependently of those resources being memory, stack, or cpu registers) of the function. But not calling return only means that the function has not filled those resources with the value to be given, the code continues executing as if it had been done (this is the source of U.B.)

So nothing special happens when you don't call return. A notable exception to this is the case of the main() function: If you don't issue a return statement, then you get the special value 0 as the return value of main. Why? because that return value is used to notify the operating system that the command you executed terminated correctly (this is a posix feature, but the standard specifies --while it don't recommends or enforces, because this is legacy--) In any case, the initialization to call main() is different as the code generated to call any other function (the difference being that for any call the code just doesn't initialize the place to be used for the return, while for main it is reserved and initialized. So if you don't use a return statement in main you can get surprised that it always returns 0. That's not required for any other function.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.