All arithmetic operator functions (+, -, *, /, %) coded only using bitwise operators in C

Question

Here's all the functions in C that does all the arithmetic operators without using arithmetic operators themselves, mostly using bitwise operators. Recursive functions and comparison operators are also allowed.

int add ( int augend, int addend )
{
    return addend ? add ( augend ^ addend, ( augend & addend ) << 1 ) : augend;
}

int subtract ( int minuend, int subtrahend )
{
    return add ( minuend, add ( ~subtrahend, 1 ) );
}

int multiply_recursive ( int multiplicand, int multiplier, int product )
{
    if ( !multiplier ) return product;
    if ( multiplier & 1 ) product = add ( multiplicand, product );
    return multiply_recursive ( multiplicand << 1, (int)( (unsigned) multiplier >> 1 ), 
                                product );
}

int multiply ( int multiplicand, int multiplier )
{
    return multiply_recursive ( multiplicand, multiplier, 0 );
}

int divide_recursive ( int dividend, int divisor, int size, int quotient, int remainder )
{
    if ( !size ) return quotient;
    int position = subtract ( size, 1 );
    remainder <<= 1;
    remainder |= ( dividend >> position ) & 1;
    if ( remainder >= divisor ) {
        remainder = subtract ( remainder, divisor );
        quotient |= 1 << position;
    }
    return divide_recursive ( dividend, divisor, position, quotient, remainder );
}

int abs ( int integer )
{
    int const mask = integer >> subtract ( multiply ( sizeof(int), 8 ), 1 );
    return add ( integer, mask ) ^ mask;
}

int divide ( int dividend, int divisor )
{
    int quotient = divide_recursive ( abs ( dividend ), abs ( divisor ), 
                                      multiply ( sizeof(int), 8 ), 0, 0 );
    return ( dividend ^ divisor ) < 0 ? add ( ~quotient, 1 ) : quotient;
}

int mod ( int dividend, int divisor )
{
    return subtract ( dividend, multiply ( divide ( dividend, divisor ), divisor ) );
}

Answer 1

Don't forget

int mod ( int dividend, int divisor )
{
    return subtract ( dividend, multiply ( divide ( dividend, divisor ), divisor ) );
}

This seems the long way around. Your divide_recursive calculates the remainder, but you forget it and then recalculate it.

Instead, consider

int mod( int dividend, int divisor )
{
    int remainder = 0;
    divide_recursive(abs(dividend), abs(divisor), multiply(sizeof(int), 8), 0, &remainder);
    return dividend < 0 ? add(~remainder, 1) : remainder;
}

That requires changing divide_recursive to take a pointer instead:

int divide_recursive( int dividend, int divisor, int size, int quotient, int *remainder )
{
    if ( !size ) return quotient;
    int position = subtract( size, 1 );
    *remainder <<= 1;
    *remainder |= ( dividend >> position ) & 1;
    if ( *remainder >= divisor ) {
        *remainder = subtract( *remainder, divisor );
        quotient |= 1 << position;
    }

    return divide_recursive( dividend, divisor, position, quotient, remainder );
}

And we need to change divide to call it correctly:

int divide( int dividend, int divisor )
{
    int remainder = 0;
    int quotient = divide_recursive( abs( dividend ), abs ( divisor ), 
                                      multiply( sizeof(int), 8 ), 0, &remainder );

    return ( dividend ^ divisor ) < 0 ? add ( ~quotient, 1 ) : quotient;
}

Too cute?

int abs ( int integer )
{
    int const mask = integer >> subtract ( multiply ( sizeof(int), 8 ), 1 );
    return add ( integer, mask ) ^ mask;
}

This also seems more complicated than necessary. Why not just say

int abs(int value)
{
    return (value > 0) ? value : add(~value, 1);
}

Why use three functions and two bitwise operations where a conditional chance of one function call is enough?

Testing

How do you know that your implementation is correct? The correct way is to write unit tests, but at minimum you need to compare your bitwise operations to the built-in operations. I wrote the following function to make sure that I was doing the math right (particularly when dealing with negative numbers):

void display_remainder(int dividend, int divisor) {
    printf("%d%%%d=%d=%d\n", dividend, divisor, mod(dividend, divisor), dividend % divisor);
}

This is not the pinnacle of coding practices, but it easily lets me see that my revised version is giving the same results as the built-in. A better, more persistent solution would be unit tests like

CU_ASSERT(-2%-3 == mod(-2, -3));

or possibly better (albeit harder to write):

CU_ASSERT(-2 == mod(-2, -3));

But either way, what's important is that you compare your results to known good results. If you publish your tests when you ask for a review, it makes it easier for us to test changes we want to propose and to suggest additional tests that show problems in the original code.

Answer 2

1. Pretty cool exercise in math theory.

2. Code relies on two's complement integers. Certainly they are common. Still, stating that dependency is good.

3. % is the C remainder function. Stating that mod() is trying to mimic that and not the classical modulus function would aid in clarity.

4. Recommend CHAR_BIT rather than 8. @Deduplicator

5. Overflow can occur with all 5 functions. Suggest documenting these functions behavior in those cases.

6. Helper functions like multiply_recursive() could be static.