Implement division with bit-wise operator

How can I implement division using bit-wise opera开发者_StackOverflowtors (not just division by powers of 2)?

Describe it in detail.

The standard way to do division is by implementing binary long-division. This involves subtraction, so as long as you don't discount this as not a bit-wise operation, then this is what you should do. (Note that you can of course implement subtraction, very tediously, using bitwise logical operations.)

In essence, if you're doing Q = N/D:

1. Align the most-significant ones of N and D.
2. Compute t = (N - D);.
3. If (t >= 0), then set the least significant bit of Q to 1, and set N = t.
4. Left-shift N by 1.
5. Left-shift Q by 1.
6. Go to step 2.

Loop for as many output bits (including fractional) as you require, then apply a final shift to undo what you did in Step 1.

Division of two numbers using bitwise operators.

#include <stdio.h>

int remainder, divisor;

int division(int tempdividend, int tempdivisor) {
    int quotient = 1;

    if (tempdivisor == tempdividend) {
        remainder = 0;
        return 1;
    } else if (tempdividend < tempdivisor) {
        remainder = tempdividend;
        return 0;
    }   

    do{

        tempdivisor = tempdivisor << 1;
        quotient = quotient << 1;

     } while (tempdivisor <= tempdividend);


     /* Call division recursively */
    quotient = quotient + division(tempdividend - tempdivisor, divisor);

    return quotient;
} 


int main() {
    int dividend;

    printf ("\nEnter the Dividend: ");
    scanf("%d", &dividend);
    printf("\nEnter the Divisor: ");
    scanf("%d", &divisor);   

    printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
    printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);
    getch();
}

int remainder =0;

int division(int dividend, int divisor)
{
    int quotient = 1;

    int neg = 1;
    if ((dividend>0 &&divisor<0)||(dividend<0 && divisor>0))
        neg = -1;

    // Convert to positive
    unsigned int tempdividend = (dividend < 0) ? -dividend : dividend;
    unsigned int tempdivisor = (divisor < 0) ? -divisor : divisor;

    if (tempdivisor == tempdividend) {
        remainder = 0;
        return 1*neg;
    }
    else if (tempdividend < tempdivisor) {
        if (dividend < 0)
            remainder = tempdividend*neg;
        else
            remainder = tempdividend;
        return 0;
    }
    while (tempdivisor<<1 <= tempdividend)
    {
        tempdivisor = tempdivisor << 1;
        quotient = quotient << 1;
    }

    // Call division recursively
    if(dividend < 0)
        quotient = quotient*neg + division(-(tempdividend-tempdivisor), divisor);
    else
        quotient = quotient*neg + division(tempdividend-tempdivisor, divisor);
     return quotient;
 }


void main()
{
    int dividend,divisor;
    char ch = 's';
    while(ch != 'x')
    {
        printf ("\nEnter the Dividend: ");
        scanf("%d", &dividend);
        printf("\nEnter the Divisor: ");
        scanf("%d", &divisor);

        printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
        printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);

        _getch();
    }
}

I assume we are discussing division of integers.

Consider that I got two number 1502 and 30, and I wanted to calculate 1502/30. This is how we do this:

First we align 30 with 1501 at its most significant figure; 30 becomes 3000. And compare 1501 with 3000, 1501 contains 0 of 3000. Then we compare 1501 with 300, it contains 5 of 300, then compare (1501-5*300) with 30. At so at last we got 5*(10^1) = 50 as the result of this division.

Now convert both 1501 and 30 into binary digits. Then instead of multiplying 30 with (10^x) to align it with 1501, we multiplying (30) in 2 base with 2^n to align. And 2^n can be converted into left shift n positions.

Here is the code:

int divide(int a, int b){
    if (b != 0)
        return;

    //To check if a or b are negative.
    bool neg = false;
    if ((a>0 && b<0)||(a<0 && b>0))
        neg = true;

    //Convert to positive
    unsigned int new_a = (a < 0) ? -a : a;
    unsigned int new_b = (b < 0) ? -b : b;

    //Check the largest n such that b >= 2^n, and assign the n to n_pwr
    int n_pwr = 0;
    for (int i = 0; i < 32; i++)
    {
        if (((1 << i) & new_b) != 0)
            n_pwr = i;
    }

    //So that 'a' could only contain 2^(31-n_pwr) many b's,
    //start from here to try the result
    unsigned int res = 0;
    for (int i = 31 - n_pwr; i >= 0; i--){
        if ((new_b << i) <= new_a){
            res += (1 << i);
            new_a -= (new_b << i);
        }
    }

    return neg ? -res : res;
}

Didn't test it, but you get the idea.

This solution works perfectly.

#include <stdio.h>

int division(int dividend, int divisor, int origdiv, int * remainder)
{
    int quotient = 1;

    if (dividend == divisor)
    {
        *remainder = 0;
        return 1;
    }

    else if (dividend < divisor)
    {
        *remainder = dividend;
        return 0;
    }

    while (divisor <= dividend)
    {
        divisor = divisor << 1;
        quotient = quotient << 1;
    }

    if (dividend < divisor)
    {
        divisor >>= 1;
        quotient >>= 1;
    }

    quotient = quotient + division(dividend - divisor, origdiv, origdiv, remainder);

    return quotient;
}

int main()
{
    int n = 377;
    int d = 7;
    int rem = 0;

    printf("Quotient : %d\n", division(n, d, d, &rem));
    printf("Remainder: %d\n", rem);

    return 0;
}

Implement division without divison operator: You will need to include subtraction. But then it is just like you do it by hand (only in the basis of 2). The appended code provides a short function that does exactly this.

uint32_t udiv32(uint32_t n, uint32_t d) {
    // n is dividend, d is divisor
    // store the result in q: q = n / d
    uint32_t q = 0;

    // as long as the divisor fits into the remainder there is something to do
    while (n >= d) {
        uint32_t i = 0, d_t = d;
        // determine to which power of two the divisor still fits the dividend
        //
        // i.e.: we intend to subtract the divisor multiplied by powers of two
        // which in turn gives us a one in the binary representation 
        // of the result
        while (n >= (d_t << 1) && ++i)
            d_t <<= 1;
        // set the corresponding bit in the result
        q |= 1 << i;
        // subtract the multiple of the divisor to be left with the remainder
        n -= d_t;
        // repeat until the divisor does not fit into the remainder anymore
    }
    return q;
}

The below method is the implementation of binary divide considering both numbers are positive. If subtraction is a concern we can implement that as well using binary operators.

Code

-(int)binaryDivide:(int)numerator with:(int)denominator
{
    if (numerator == 0 || denominator == 1) {
        return numerator;
    }

    if (denominator == 0) {

        #ifdef DEBUG
            NSAssert(denominator == 0, @"denominator should be greater then 0");
        #endif
        return INFINITY;
    }

    // if (numerator <0) {
    //     numerator = abs(numerator);
    // }

    int maxBitDenom = [self getMaxBit:denominator];
    int maxBitNumerator = [self getMaxBit:numerator];
    int msbNumber = [self getMSB:maxBitDenom ofNumber:numerator];

    int qoutient = 0;

    int subResult = 0;

    int remainingBits = maxBitNumerator-maxBitDenom;

    if (msbNumber >= denominator) {
        qoutient |=1;
        subResult = msbNumber - denominator;
    }
    else {
        subResult = msbNumber;
    }

    while (remainingBits>0) {
        int msbBit = (numerator & (1 << (remainingBits-1)))>0 ? 1 : 0;
        subResult = (subResult << 1) |msbBit;
        if (subResult >= denominator) {
            subResult = subResult-denominator;
            qoutient = (qoutient << 1) | 1;
        }
        else {
            qoutient = qoutient << 1;
        }
        remainingBits--;
    }
    return qoutient;
}


-(int)getMaxBit:(int)inputNumber
{
    int maxBit =0;
    BOOL isMaxBitSet = NO;
    for (int i=0; i<sizeof(inputNumber)*8; i++) {
        if (inputNumber & (1 << i) ) {
            maxBit = i;
            isMaxBitSet=YES;
        }
    }
    if (isMaxBitSet) {
        maxBit += 1;
    }
    return maxBit;
}


-(int)getMSB:(int)bits ofNumber:(int)number
{
    int numbeMaxBit = [self getMaxBit:number];
    return number >> (numbeMaxBit -bits);
}

For integers:

public class Division {

    public static void main(String[] args) {
        System.out.println("Division: " + divide(100, 9));
    }

    public static int divide(int num, int divisor) {
        int sign = 1;
        if((num > 0 && divisor < 0) || (num < 0 && divisor > 0))
            sign = -1;

        return divide(Math.abs(num), Math.abs(divisor), Math.abs(divisor)) * sign;
    }

    public static int divide(int num, int divisor, int sum) {
        if (sum > num) {
            return 0;
        }

        return 1 + divide(num, divisor, sum + divisor);
    }
}

With the usual caveats about C's behaviour with shifts, this ought to work for unsigned quantities regardless of the native size of an int...

static unsigned int udiv(unsigned int a, unsigned int b) {
  unsigned int c = 1, result = 0;

  if (b == 0) return (unsigned int)-1 /*infinity*/;

  while (((int)b > 0) && (b < a)) { b = b<<1; c = c<<1; }

  do {
    if (a >= b) { a -= b; result += c; }
    b = b>>1; c = c>>1;
  } while (c);

  return result;
}

This is my solution to implement division with only bitwise operations:

int align(int a, int b) {
  while (b < a) b <<= 1;
  return b;
}

int divide(int a, int b) {
  int temp = b;
  int result = 0;
  b = align(a, b);
  do {
    result <<= 1;
    if (a >= b) {
      // sub(a,b) is a self-defined bitwise function for a minus b
      a = sub(a,b);
      result = result | 1;
    }
    b >>= 1;
  } while (b >= temp);
  return result;
}

Unsigned Long Division (JavaScript) - based on Wikipedia article: https://en.wikipedia.org/wiki/Division_algorithm: "Long division is the standard algorithm used for pen-and-paper division of multi-digit numbers expressed in decimal notation. It shifts gradually from the left to the right end of the dividend, subtracting the largest possible multiple of the divisor (at the digit level) at each stage; the multiples then become the digits of the quotient, and the final difference is then the remainder. When used with a binary radix, this method forms the basis for the (unsigned) integer division with remainder algorithm below."

Function divideWithoutDivision at the end wraps it to allow negative operands. I used it to solve leetcode problem "Product of Array Except Self"

function longDivision(N, D) {
    let Q = 0; //quotient and remainder
    let R = 0;
    let n = mostSignificantBitIn(N);
    for (let i = n; i >= 0; i--) { 
        R = R << 1;
        R = setBit(R, 0, getBit(N, i));
        if (R >= D) {
            R = R - D;
            Q = setBit(Q, i, 1);
        }
    }
    //return [Q, R];
    return Q;
}
function mostSignificantBitIn(N) {
    for (let i = 31; i >= 0; i--) {
        if (N & (1 << i))
            return i ;
    }
    return 0;
}
function getBit(N, i) {
    return (N & (1 << i)) >> i;
}
function setBit(N, i, value) {
    return N | (value << i);
}
function divideWithoutDivision(dividend, divisor) {
    let negativeResult = (dividend < 0) ^ (divisor < 0);
    dividend = Math.abs(dividend);
    divisor = Math.abs(divisor);
    let quotient = longDivision(dividend, divisor);
    return negativeResult ? -quotient : quotient;
}

All these solutions are too long. The base idea is to write the quotient (for example, 5=101) as 100 + 00 + 1 = 101.

public static Point divide(int a, int b) {

    if (a < b)
        return new Point(0,a);
    if (a == b)
        return new Point(1,0);
    int q = b;
    int c = 1;
    while (q<<1 < a) {
        q <<= 1;
        c <<= 1;
    }
    Point r = divide(a-q, b);
    return new Point(c + r.x, r.y);
}


public static class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int compare(Point b) {
        if (b.x - x != 0) {
            return x - b.x;
        } else {
            return y - b.y;
        }
    }

    @Override
    public String toString() {
        return " (" + x + " " + y + ") ";
    }
}

Since bit wise operations work on bits that are either 0 or 1, each bit represents a power of 2, so if I have the bits

1010

that value is 10.

Each bit is a power of two, so if we shift the bits to the right, we divide by 2

1010 --> 0101

0101 is 5

so, in general if you want to divide by some power of 2, you need to shift right by the exponent you raise two to, to get that value

so for instance, to divide by 16, you would shift by 4, as 2^^4 = 16.