Thread: Hodor Can Divide

I'm not really sure how to deal with division by zero. I could exit() with a message I guess...

Edit: I originally used bitshifts and bitwise operators

Code:

/*
 * Integer division function
 * 
 * By Hodor, 2013
 * 
 */
#include <stdio.h>
#include <assert.h>

#define ZABS(n)     ( (n) < 0 ? (-n) : (n) )

int idivide(int a, int b);

int main(void)
{
    int i, j;

    for (i = -6000; i < 6000; i++) {
        for (j = -6000; j < 6000; j++) {
            if (j == 0)
                continue;
            assert(idivide(i, j) == i / j);
        }
    }

    return 0;
}

int idivide(int a, int b)
{
    unsigned quotient = 0;
    unsigned dividend, divisor, step;
    unsigned short neganswer = (a < 0) != (b < 0);
    
    dividend = ZABS(a);
    divisor  = ZABS(b);
    
    if (dividend < divisor)
        return 0;
    if (dividend == divisor)
        return neganswer ? -1 : 1;
    if (divisor == 0)
        return 0;       /* Implementation defined behaviour for div by 0 :) */
    
    /* Align left most bit of divisor with dividend
     */
    step = 1;
    while (divisor <= dividend) {
        step *= 2;
        divisor *= 2;
    }
    
    while (step != 0) {
        if (dividend >= divisor) {
            quotient += step; /* original: quotient |= step; */
            dividend -= divisor;
        }
        step /= 2;
        divisor /= 2;
    }
    
    return neganswer ? -quotient : quotient;
}

Non-restoring signed divide as implemented on an old 16 bit mini computer, without the overflow checks. Quotients are rounded down towards -∞ (as opposed to C99, which rounds towards zero). Shorts are assumed to be 16 bits, ints to be 32 bits.

Code:

#include <stdio.h>

unsigned int divide(unsigned int dvnd, unsigned short dvsr)
{
int i;
unsigned short qb;                  /* quotient bit */
unsigned short q;                   /* quotient */

    if(dvsr>>15)                    /* if dvsr negative, decrement dvnd */
        dvnd -= 1;
    q = 0;
    qb = (dvnd>>31) == (dvsr>>15);  /* if signs same, qb = 1, else qb = 0 */
                                    /*  and if signs same, subtract, else add */
    i = 0;
    while(1){
        dvnd = qb ? dvnd - ((unsigned int)dvsr<<16) : dvnd + ((unsigned int)dvsr<<16);
        qb = (dvnd>>31) == (dvsr>>15);
        q = (q<<1) | qb;
        if(++i == 17)
            break;
        dvnd <<= 1;
    }
    if((dvnd>>31) != (dvsr>>15))    /* if remainder wrong sign, add dvsr */
        dvnd += (unsigned int)dvsr<<16;
    if(dvsr>>15)                    /* if dvsr negative, increment remainder */
        dvnd += 0x10000;
    return(dvnd | q);
}

int main(){
char buffer[80];
unsigned int m0, m1;
    while(1){
        printf("enter numbers in hex: ");
        fgets(buffer, sizeof(buffer), stdin);
        if(2 != sscanf(buffer, "%x %x", &m0, &m1))
            break;
        m0 = divide(m0, (unsigned short)m1);
        printf("quotient is: %4x  remainder is %4x\n", m0 & 0xffff, m0>>16);
    }
    return 0;
}