Implement division with bit-wise operator

Question

How can I implement division using bit-wise operators  not just division by powers of 2    Describe it in detail

User · Answer

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.

User · Answer

Division of two numbers using bitwise operators      include  lt stdio h gt   int remainder  divisor   int division int tempdividend  int tempdivisor        int quotient   1       if  tempdivisor    tempdividend            remainder   0          return 1        else if  tempdividend  lt  tempdivisor            remainder   tempdividend          return 0                do           tempdivisor   tempdivisor  lt  lt  1          quotient   quotient  lt  lt  1          while  tempdivisor  lt   tempdividend             Call division recursively        quotient   quotient   division tempdividend - tempdivisor  divisor        return quotient       int main         int dividend       printf    nEnter the Dividend          scanf   d    amp dividend       printf   nEnter the Divisor          scanf   d    amp divisor           printf   n d    d  quotient    d   dividend  divisor  division dividend  divisor        printf   n d    d  remainder    d   dividend  divisor  remainder       getch

User · Answer

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  gt  0  amp  amp  divisor  lt  0      num  lt  0  amp  amp  divisor  gt  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  gt  num                return 0                     return 1   divide num  divisor  sum   divisor

User · Answer

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

User · Answer

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  gt  0   amp  amp   b  lt  a     b   b lt  lt 1  c   c lt  lt 1       do       if  a  gt   b    a -  b  result    c        b   b gt  gt 1  c   c gt  gt 1      while  c      return result

User · Answer

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  lt  b          return new Point 0 a       if  a    b          return new Point 1 0       int q   b      int c   1      while  q lt  lt 1  lt  a            q  lt  lt   1          c  lt  lt   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

User · Answer

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    quot denominator should be greater then 0 quot             endif         return INFINITY                if  numerator  lt 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  gt   denominator            qoutient   1          subResult   msbNumber - denominator            else           subResult   msbNumber             while  remainingBits gt 0            int msbBit    numerator  amp   1  lt  lt   remainingBits-1    gt 0   1   0          subResult    subResult  lt  lt  1   msbBit          if  subResult  gt   denominator                subResult   subResult-denominator              qoutient    qoutient  lt  lt  1    1                    else               qoutient   qoutient  lt  lt  1                    remainingBits--            return qoutient      - int getMaxBit  int inputNumber       int maxBit  0      BOOL isMaxBitSet   NO      for  int i 0  i lt sizeof inputNumber  8  i              if  inputNumber  amp   1  lt  lt  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  gt  gt   numbeMaxBit -bits

User · Answer

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    Align the most-significant ones of N and D  Compute t    N - D    If  t  gt   0   then set the least significant bit of Q to 1  and set N   t  Left-shift N by 1  Left-shift Q by 1  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

User · Answer

int remainder  0   int division int dividend  int divisor        int quotient   1       int neg   1      if   dividend gt 0  amp  amp divisor lt 0    dividend lt 0  amp  amp  divisor gt 0           neg   -1          Convert to positive     unsigned int tempdividend    dividend  lt  0    -dividend   dividend      unsigned int tempdivisor    divisor  lt  0    -divisor   divisor       if  tempdivisor    tempdividend            remainder   0          return 1 neg            else if  tempdividend  lt  tempdivisor            if  dividend  lt  0              remainder   tempdividend neg          else             remainder   tempdividend          return 0            while  tempdivisor lt  lt 1  lt   tempdividend                tempdivisor   tempdivisor  lt  lt  1          quotient   quotient  lt  lt  1                Call division recursively     if dividend  lt  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    amp dividend           printf   nEnter the Divisor              scanf   d    amp divisor            printf   n d    d  quotient    d   dividend  divisor  division dividend  divisor            printf   n d    d  remainder    d   dividend  divisor  remainder             getch

User · Answer

This solution works perfectly      include  lt stdio h gt   int division int dividend  int divisor  int origdiv  int   remainder        int quotient   1       if  dividend    divisor                 remainder   0          return 1             else if  dividend  lt  divisor                 remainder   dividend          return 0             while  divisor  lt   dividend                divisor   divisor  lt  lt  1          quotient   quotient  lt  lt  1             if  dividend  lt  divisor                divisor  gt  gt   1          quotient  gt  gt   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   amp rem        printf  Remainder   d n   rem        return 0

User · Answer

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  gt   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  gt    d t  lt  lt  1   amp  amp    i              d t  lt  lt   1             set the corresponding bit in the result         q    1  lt  lt  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

[bit-manipulation] Implement division with bit-wise operator

Examples related to bit-manipulation

Examples related to bit