How can I multiply and divide using only bit shifting and adding

Question

User · Answer

The answer by Andrew Toulouse can be extended to division.

The division by integer constants is considered in details in the book "Hacker's Delight" by Henry S. Warren (ISBN 9780201914658).

The first idea for implementing division is to write the inverse value of the denominator in base two.

E.g., 1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....

So, a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30) for 32-bit arithmetics.

By combining the terms in an obvious manner we can reduce the number of operations:

b = (a >> 2) + (a >> 4)

b += (b >> 4)

b += (b >> 8)

b += (b >> 16)

There are more exciting ways to calculate division and remainders.

EDIT1:

If the OP means multiplication and division of arbitrary numbers, not the division by a constant number, then this thread might be of use: https://stackoverflow.com/a/12699549/1182653

EDIT2:

One of the fastest ways to divide by integer constants is to exploit the modular arithmetics and Montgomery reduction: What's the fastest way to divide an integer by 3?

User · Answer

This should work for multiplication    data   text  globl  main  main      4    5    2      addi  4   0  0x9     addi  5   0  0x6      add   2   0   0   initialize product to zero  Loop         beq   5   0  Exit   if multiplier is 0 terminate loop     andi  3   5  1   mask out the 0th bit in multiplier     beq   3   0  Shift   if the bit is 0  skip add     addu  2   2   4   add  shifted  multiplicand to product  Shift       sll  4   4  1   shift up the multiplicand 1 bit     srl  5   5  1   shift down the multiplier 1 bit     j Loop   go for next    Exit      EXIT   li  v0 10 syscall

User · Answer

I translated the Python code to C  The example given had a minor flaw  If the dividend value that took up all the 32 bits  the shift would fail  I just used 64-bit variables internally to work around the problem   int No divide int nDivisor  int nDividend  int  nRemainder        int nQuotient   0      int nPos   -1      unsigned long long ullDivisor   nDivisor      unsigned long long ullDividend   nDividend       while  ullDivisor  lt   ullDividend                ullDivisor  lt  lt   1          nPos                ullDivisor  gt  gt   1       while  nPos  gt  -1                if  ullDividend  gt   ullDivisor                        nQuotient     1  lt  lt  nPos               ullDividend -  ullDivisor                     ullDivisor  gt  gt   1          nPos -  1              nRemainder    int  ullDividend       return nQuotient

User · Answer

Taken from here    This is only for division   int add int a  int b            int partialSum  carry          do               partialSum   a   b              carry    a  amp  b   lt  lt  1              a   partialSum              b   carry            while  carry    0           return partialSum     int subtract int a  int b        return add a  add  b  1       int division int dividend  int divisor            boolean negative   false          if   dividend  amp   1  lt  lt  31       1  lt  lt  31        Check for signed bit             negative    negative              dividend   add  dividend  1       Negation                   if   divisor  amp   1  lt  lt  31       1  lt  lt  31                 negative    negative              divisor   add  divisor  1       Negation                   int quotient   0          long r          for  int i   30  i  gt   0  i   subtract i  1                 r    divisor  lt  lt  i                 Left shift divisor until it s smaller than dividend             if  r  lt  Integer MAX VALUE  amp  amp  r  gt   0       Avoid cases where comparison between long and int doesn t make sense                 if  r  lt   dividend                         quotient     1  lt  lt  i                           dividend   subtract dividend   int  r                                                     if  negative                quotient   add  quotient  1                     return quotient

User · Answer

x  lt  lt  k    x multiplied by 2 to the power of k x  gt  gt  k    x divided by 2 to the power of k  You can use these shifts to do any multiplication operation  For example   x   14    x   16 - x   2     x  lt  lt  4  -  x  lt  lt  1  x   12    x   8   x   4     x  lt  lt  3     x  lt  lt  2   To divide a number by a non-power of two  I m not aware of any easy way  unless you want to implement some low-level logic  use other binary operations and use some form of iteration

User · Answer

Try this  https   gist github com swguru 5219592  import sys   implement divide operation without using built-in divide operator def divAndMod slow y x  debug 0       r   0     while y  gt   x              r    1             y -  x     return r y      implement divide operation without using built-in divide operator def divAndMod y x  debug 0           find the highest position of positive bit of the ratio     pos   -1     while y  gt   x              pos    1             x  lt  lt   1     x  gt  gt   1     if debug  print  y  d  x  d  pos  d     y x pos       if pos    -1              return 0  y      r   0     while pos  gt   0              if y  gt   x                      r     1  lt  lt  pos                                              y -  x                             if debug  print  y  d  x  d  r  d  pos  d     y x r pos               x  gt  gt   1             pos -  1      return r  y   if   name        main         if len sys argv     3          y   int sys argv 1           x   int sys argv 2        else              y   313271356             x   7  print      Slow Version       res   divAndMod slow  y  x  print   d    d    d    d     y  x  res 0   res 1    print      Fast Version       res   divAndMod  y  x  debug 1  print   d    d    d    d     y  x  res 0   res 1

User · Answer

it is basically multiplying and dividing with the base power 2  shift left   x   2   y  shift right   x   2   y  shl eax 2    2   2   2   8  shr eax 3    2   2   3   1 4

User · Answer

A procedure for dividing integers that uses shifts and adds can be derived in straightforward fashion from decimal longhand division as taught in elementary school  The selection of each quotient digit is simplified  as the digit is either 0 and 1  if the current remainder is greater than or equal to the divisor  the least significant bit of the partial quotient is 1   Just as with decimal longhand division  the digits of the dividend are considered from most significant to least significant  one digit at a time  This is easily accomplished by a left shift in binary division  Also  quotient bits are gathered by left shifting the current quotient bits by one position  then appending the new quotient bit    In a classical arrangement  these two left shifts are combined into left shifting of one register pair  The upper half holds the current remainder  the lower half initial holds the dividend  As the dividend bits are transferred to the remainder register by left shift  the unused least significant bits of the lower half are used to accumulate the quotient bits   Below is x86 assembly language and C implementations of this algorithm  This particular variant of a shift  amp  add division is sometimes referred to as the  no-performing  variant  as the subtraction of the divisor from the current remainder is not performed unless the remainder is greater than or equal to the divisor  In C  there is no notion of the carry flag used by the assembly version in the register pair left shift  Instead  it is emulated  based on the observation that the result of an addition modulo 2n can be smaller that either addend only if there was a carry out    include  lt stdio h gt   include  lt stdlib h gt   include  lt stdint h gt    define USE ASM 0   if USE ASM uint32 t bitwise division  uint32 t dividend  uint32 t divisor        uint32 t quot        asm           mov  eax   dividend     quot   dividend         mov  ecx   divisor      divisor         mov  edx  32            bits left         mov  ebx  0             rem      div loop          add  eax  eax            rem quot   lt  lt  1         adc  ebx  ebx                        cmp  ebx  ecx           rem  gt   divisor           jb   quot bit is 0      if  rem  lt  divisor       quot bit is 1                       sub  ebx  ecx           rem   rem - divisor         add  eax  1             quot        quot bit is 0          dec  edx                bits left--         jnz   div loop          while  bits left          mov   quot   eax        quot                       return quot     else uint32 t bitwise division  uint32 t dividend  uint32 t divisor        uint32 t quot  rem  t      int bits left   CHAR BIT   sizeof  uint32 t        quot   dividend      rem   0      do                   rem quot   lt  lt  1             t   quot              quot   quot   quot              rem   rem   rem    quot  lt  t                if  rem  gt   divisor                    rem   rem - divisor                  quot   quot   1                            bits left--        while  bits left       return quot     endif

User · Answer

To multiply in terms of adding and shifting you want to decompose one of the numbers by powers of two  like so   21   5   10101 2   101 2              Initial step           10101 2    1   2 2     0   2 1     1   2 0           10101 2   2 2   10101 2   2 0           10101 2  lt  lt  2   10101 2  lt  lt  0  Decomposed           10101 2   4   10101 2   1          10101 2   5          21   5                       Same as initial expression      2 means base 2   As you can see  multiplication can be decomposed into adding and shifting and back again  This is also why multiplication takes longer than bit shifts or adding - it s O n 2  rather than O n  in the number of bits  Real computer systems  as opposed to theoretical computer systems  have a finite number of bits  so multiplication takes a constant multiple of time compared to addition and shifting  If I recall correctly  modern processors  if pipelined properly  can do multiplication just about as fast as addition  by messing with the utilization of the ALUs  arithmetic units  in the processor

User · Answer

For anyone interested in a 16-bit x86 solution  there is a piece of code by JasonKnight here1  he also includes a signed multiply piece  which I haven t tested   However  that code has issues with large inputs  where the  add bx bx  part would overflow   The fixed version   softwareMultiply       INPUT  CX BX     OUTPUT  DX AX - 32 bits   CLOBBERS  BX CX DI     xor   ax ax       cheap way to zero a reg     mov   dx ax       1 clock faster than xor     mov   di cx     or    di bx       cheap way to test for zero on both regs     jz     done     mov   di ax       DI used for reg reg adc  loop      shr   cx 1        divide by two  bottom bit moved to carry flag     jnc    skipAddToResult     add   ax bx     adc   dx di       reg reg is faster than reg imm16  skipAddToResult      add   bx bx       faster than shift or mul     adc   di di     or    cx cx       fast zero check     jnz    loop  done      ret   Or the same in GCC inline assembly   asm  mov  0   ax n t       mov  0   dx n t       mov   cx   di n t       or   bx   di n t       jz done n t       mov   ax   di n t       loop  n t       shr  1   cx n t       jnc skipAddToResult n t       add   bx   ax n t       adc   di   dx n t       skipAddToResult  n t       add   bx   bx n t       adc   di   di n t       or   cx   cx n t       jnz loop n t       done  n t          d   dx     a   ax         b   bx    c   cx         ecx    edi

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      For multiplication  - int multiplyNumber  int num1 withNumber  int num2       int mulResult   0      int ithBit       BOOL isNegativeSign    num1 lt 0  amp  amp  num2 gt 0      num1 gt 0  amp  amp  num2 lt 0       num1   abs num1       num2   abs num2         for  int i 0  i lt sizeof num2  8  i                  ithBit    num2  amp   1 lt  lt i           if  ithBit gt 0                mulResult     num1  lt  lt  i                         if  isNegativeSign            mulResult       mulResult  1              return mulResult

User · Answer

Take two numbers  lets say 9 and 10  write them as binary - 1001 and 1010   Start with a result  R  of 0   Take one of the numbers  1010 in this case  we ll call it A  and shift it right by one bit  if you shift out a one  add the first number  we ll call it B  to R   Now shift B left by one bit and repeat until all bits have been shifted out of A   It s easier to see what s going on if you see it written out  this is the example         0    0000      0   10010      1  000000      0 1001000      1  ------ 1011010

User · Answer

A left shift by 1 position is analogous to multiplying by 2  A right shift is analogous to dividing by 2  You can add in a loop to multiply  By picking the loop variable and the addition variable correctly  you can bound performance  Once you ve explored that  you should use Peasant Multiplication

User · Answer

X   2   1 bit shift left X   2   1 bit shift right X   3   shift left 1 bit and then add X

[c] How can I multiply and divide using only bit shifting and adding?

Examples related to c

Examples related to assembly

Examples related to bit-manipulation

Examples related to division

Examples related to multiplication