/** bitmath.c -- by James D. Lin (last updated: 2006-02-15)
  *
  *     Performs +, -, *, / operations using only bitwise operators.
  *     (Why?  Because I was bored.)
  */

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


typedef unsigned int uint;

static int negate(int);
static uint countBits(uint);

static int add(int, int);
static int subtract(int, int);
static int multiply(int, int);
static int divide(int, int);

static uint remainder = 0;


int main(int argc, char* argv[])
{
    char mode;
    int a, b;

    /* Function pointer. */
    int (*op)(int, int);

    if (argc != 4)
    {
        fprintf(stderr,
                "Usage: %s <a> <op> <b>\n"
                "Where <op> is one of: + - x /\n",
                argv[0]);
        return EXIT_FAILURE;
    }

    /* Parse command-line arguments. */
    mode = argv[2][0];
    a = atoi(argv[1]);
    b = atoi(argv[3]);

    switch (mode)
    {
        case '+' :
            op = add;
            break;
        case '-' :
            op = subtract;
            break;

        /* Accept 'x' since shell wildcard expansion can make '*'
         * inconvenient.
         */
        case 'x' :
        case '*' :
            op = multiply;
            break;
        case '/' :
            op = divide;
            break;
        default :
            fprintf(stderr, "Invalid mode.\n");
            return EXIT_FAILURE;
    }

    /* Output results. */
    printf("%d %c %d = %d", a, mode, b, op(a, b));
    if (remainder != 0)
    {
        printf(" R %u", remainder);
    }
    putchar('\n');

    return EXIT_SUCCESS;
}


int negate(int x)
{
    /* Assume two's-complement negatives. */
    return add(~x, 1);
}


uint countBits(uint x)
{
    uint n = 0;
    while (x != 0)
    {
        x >>= 1;
        n = add(n, 1);
    }
    return n;
}


int add(int a, int b)
{
    int carryBits;
    while (a != 0 && b != 0)
    {
        carryBits = (a & b) << 1;
        a ^= b;
        b = carryBits;
    }
    return (b == 0) ? a : b;
}


int subtract(int a, int b)
{
    return add(a, negate(b));
}


int multiply(int a, int b)
{
    int result = 0;
    while (b != 0)
    {
        if (b & 0x1)
        {
            result = add(result, a);
        }
        a <<= 1;
        b = ((uint) b) >> 1;
    }
    return result;
}


/* For brevity, divide does not handle negative numbers. */
int divide(int dividend, int divisor)
{
    int quotient = 0;
    int shiftAmt, partial;
    uint digit;

    if (divisor == 0)
    {
        fprintf(stderr, "ERROR: divide-by-zero\n");
        exit(EXIT_FAILURE);
    }

    shiftAmt = subtract(countBits(dividend),
                        countBits(divisor));

    if (shiftAmt >= 0)
    {
        digit = 1 << shiftAmt;
        partial = (uint) divisor << shiftAmt;

        while (digit != 0)
        {
            if (partial <= dividend)
            {
                quotient |= digit;
                dividend = subtract(dividend, partial);
            }
            digit >>= 1;
            partial = ((uint) partial) >> 1;
        }
    }
    remainder = dividend;
    return quotient;
}