 # 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