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

by

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 << 2 + 10101_2 << 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.

More Related Contents:

  1. Division result is always zero [duplicate]
  2. Catch and compute overflow during multiplication of two large integers
  3. Extracting bits with a single multiplication
  4. Why does mulss take only 3 cycles on Haswell, different from Agner’s instruction tables? (Unrolling FP loops with multiple accumulators)
  5. How to get c code to execute hex machine code?
  6. Rounding up to next power of 2
  7. Why is there no “sub rsp” instruction in this function prologue and why are function parameters stored at negative rbp offsets?
  8. Is multiplication and division using shift operators in C actually faster?
  9. SIMD signed with unsigned multiplication for 64-bit * 64-bit to 128-bit
  10. Bitwise operators and “endianness”
  11. What is the instruction that gives branchless FP min and max on x86?
  12. Why are global variables in x86-64 accessed relative to the instruction pointer?
  13. Unexpected exec permission from mmap when assembly files included in the project
  14. Why is the value of EDX overwritten when making call to printf?
  15. What is the purpose of the RBP register in x86_64 assembler?
  16. What is the fastest way to convert float to int on x86
  17. Alloca implementation
  18. How can I multiply 64 bit operands and get 128 bit result portably?
  19. Why GCC compiled C program needs .eh_frame section?
  20. What’s a good C decompiler? [closed]
  21. C reverse bits in unsigned integer
  22. Why we need Clobbered registers list in Inline Assembly?
  23. Very fast memcpy for image processing?
  24. Compiler changes printf to puts
  25. Linux Shellcode “Hello, World!”
  26. Linux system call table or cheatsheet for Assembly [closed]
  27. How to print exact value of the program counter in C
  28. Printf without newline in assembly
  29. What is the effect of second argument in _builtin_prefetch()?
  30. How sqrt() of GCC works after compiled? Which method of root is used? Newton-Raphson?

Leave a Comment