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

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

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 gt 0  amp  amp  b lt 0    a lt 0  amp  amp  b gt 0           neg   true         Convert to positive     unsigned int new a    a  lt  0    -a   a      unsigned int new b    b  lt  0    -b   b         Check the largest n such that b  gt   2 n  and assign the n to n pwr     int n pwr   0      for  int i   0  i  lt  32  i                  if    1  lt  lt  i   amp  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  gt   0  i--           if   new b  lt  lt  i   lt   new a               res     1  lt  lt  i               new a -   new b  lt  lt  i                        return neg   -res   res      Didn t test it  but you get the idea

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

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

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

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

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

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

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

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

Code

Examples related to bit-manipulation

Examples related to bit