# division_with_shift_operator_v1.c

Aug 16th, 2020
123
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2.
3.     division_with_shift_operator_v1.c
4.
5. https://www.geeksforgeeks.org/divide-two-integers-without-using-multiplication-division-mod-operator/
6. https://www.go4expert.com/articles/using-shift-operator-faster-division-t3095/
7. https://www.tutorialspoint.com/cprogramming/c_bitwise_operators.htm
8.
9.     The Joyful Programmer:
10. Old optimization statement that I learned many, many, many
11. years ago, when reading an optimization book by Michael Abrash. It goes:
12.
13. "Multiply if you must, but never divide."
14.
15. Remove the multiplication operator. Why? Well,
16. when C++ is reduced to machine language, it takes the processor (newer ones)
17. about 30 clock cycles to execute a single multiplication. Division takes over
18. 60 clock cycles. However, we can reduce the amount of clock cycles by using a
19. shift operator.
20.
21. That's only 2 clock cycles versus an estimated 30 clock cycles, a 28 clock
22. cycle difference, which could be essential if you are doing millions of
23. calculations.
24.
25.
26.     You can find all my C programs at Dragan Milicev's pastebin:
27.
28.     https://pastebin.com/u/dmilicev
29.
30. */
31.
32. #include <stdio.h>
33.
34. // Function to divide dividend by divisor and return floor value it
35. int divide_v1(int dividend, int divisor)
36. {
37.     // Calculate sign of divisor i.e. sign will be negative only if
38.     // either one of them is negative otherwise it will be positive
39.     int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
40.
41.     // Update both divisor and dividend positive
42.     dividend = abs(dividend);
43.     divisor = abs(divisor);
44.
45.     // Initialize the quotient
46.     int quotient = 0;
47.
48.     while (dividend >= divisor)
49.     {
50.         dividend -= divisor;
51.         ++quotient;
52.     }
53.
54.     return sign * quotient;
55. }
56.
57. // Function to divide dividend by divisor and return floor value it
58. int divide_v2(long long dividend, long long divisor)
59. {
60.     int i;
61.
62.     // Calculate sign of divisor i.e., sign will be negative only if
63.     // either one of them is negative otherwise it will be positive
64.     int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
65.
66.     // remove sign of operands
67.     dividend = abs(dividend);
68.     divisor = abs(divisor);
69.
70.     // Initialize the quotient
71.     long long quotient = 0, temp = 0;
72.
73.     // test down from the highest bit and accumulate the tentative value for valid bit
74.     for (i=31; i>=0; --i)
75.     {
76.         if (temp + (divisor << i) <= dividend)
77.         {
78.             temp += divisor << i;
79.             quotient |= 1LL << i;
80.         }
81.     }
82.
83.     return sign * quotient;
84. }
85.
86.
87. int main(void)
88. {
89.     int n = 36 , m = 12;
90.
91.     printf(" %d / %d = %d \n", n, m, divide_v1(n, m) );
92.
93.     printf(" %d / %d = %d \n", n, m, divide_v2(n, m) );
94.
95.     return 0;
96.
97. } // main()
98.
RAW Paste Data Copied