dmilicev

multiplication_with_shift_operator_v1.c

Aug 16th, 2020
112
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3.     multiplication_with_shift_operator_v1.c
  4.  
  5.     https://www.geeksforgeeks.org/multiplication-two-numbers-shift-operator/
  6.     https://www.geeksforgeeks.org/left-shift-right-shift-operators-c-cpp/
  7.  
  8.     How the C/C++ << and >> Shift Operators Work
  9.     https://www.eeweb.com/profile/max-maxfield/articles/how-the-c-c-shift-operators-work
  10.  
  11.     Left shifting an integer “x” with an integer “y” (x<<y)
  12.     is equivalent to multiplying x with 2^y (2 raise to power y).
  13.  
  14.     Similarly right shifting (x>>y) is equivalent to dividing x with 2^y.
  15.  
  16.     The Joyful Programmer:
  17. Old optimization statement that I learned many, many, many
  18. years ago, when reading an optimization book by Michael Abrash. It goes:
  19.  
  20. "Multiply if you must, but never divide."
  21.  
  22. Remove the multiplication operator. Why? Well,
  23. when C++ is reduced to machine language, it takes the processor (newer ones)
  24. about 30 clock cycles to execute a single multiplication. Division takes over
  25. 60 clock cycles. However, we can reduce the amount of clock cycles by using a
  26. shift operator.
  27.  
  28. That's only 2 clock cycles versus an estimated 30 clock cycles, a 28 clock
  29. cycle difference, which could be essential if you are doing millions of
  30. calculations.
  31.  
  32.  
  33.     There are also opposing opinions:
  34.     Is multiplication and division using shift operators in C actually faster?
  35.     This depends on the processor and the compiler. Some compilers already
  36.     optimize code this way, others don't. So you need to check each time
  37.     your code needs to be optimized this way.
  38.     https://stackoverflow.com/questions/6357038/is-multiplication-and-division-using-shift-operators-in-c-actually-faster
  39.  
  40.  
  41.     You can find all my C programs at Dragan Milicev's pastebin:
  42.  
  43.     https://pastebin.com/u/dmilicev
  44.  
  45. */
  46.  
  47. #include <stdio.h>
  48.  
  49. int multiply(int n, int m)
  50. {
  51.     int ans = 0, count = 0;
  52.     while (m)
  53.     {
  54.         if (m % 2 == 1)         // check for set bit and left
  55.             ans += n << count;  // shift n, count times
  56.  
  57.         count++;                // increment of place value (count)
  58.         m /= 2;
  59.     }
  60.     return ans;
  61. }
  62.  
  63. int main(void)
  64. {
  65.     int n = 20 , m = 13;
  66.  
  67.     printf("\n %d * %d = %d \n", n, m, multiply(n, m) );
  68.  
  69.  
  70.     return 0;
  71.  
  72. } // main()
  73.  
RAW Paste Data Copied