Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- division_with_shift_operator_v1.c
- https://www.geeksforgeeks.org/divide-two-integers-without-using-multiplication-division-mod-operator/
- https://www.go4expert.com/articles/using-shift-operator-faster-division-t3095/
- https://www.tutorialspoint.com/cprogramming/c_bitwise_operators.htm
- The Joyful Programmer:
- Old optimization statement that I learned many, many, many
- years ago, when reading an optimization book by Michael Abrash. It goes:
- "Multiply if you must, but never divide."
- Remove the multiplication operator. Why? Well,
- when C++ is reduced to machine language, it takes the processor (newer ones)
- about 30 clock cycles to execute a single multiplication. Division takes over
- 60 clock cycles. However, we can reduce the amount of clock cycles by using a
- shift operator.
- That's only 2 clock cycles versus an estimated 30 clock cycles, a 28 clock
- cycle difference, which could be essential if you are doing millions of
- calculations.
- You can find all my C programs at Dragan Milicev's pastebin:
- https://pastebin.com/u/dmilicev
- */
- #include <stdio.h>
- // Function to divide dividend by divisor and return floor value it
- int divide_v1(int dividend, int divisor)
- {
- // Calculate sign of divisor i.e. sign will be negative only if
- // either one of them is negative otherwise it will be positive
- int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
- // Update both divisor and dividend positive
- dividend = abs(dividend);
- divisor = abs(divisor);
- // Initialize the quotient
- int quotient = 0;
- while (dividend >= divisor)
- {
- dividend -= divisor;
- ++quotient;
- }
- return sign * quotient;
- }
- // Function to divide dividend by divisor and return floor value it
- int divide_v2(long long dividend, long long divisor)
- {
- int i;
- // Calculate sign of divisor i.e., sign will be negative only if
- // either one of them is negative otherwise it will be positive
- int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
- // remove sign of operands
- dividend = abs(dividend);
- divisor = abs(divisor);
- // Initialize the quotient
- long long quotient = 0, temp = 0;
- // test down from the highest bit and accumulate the tentative value for valid bit
- for (i=31; i>=0; --i)
- {
- if (temp + (divisor << i) <= dividend)
- {
- temp += divisor << i;
- quotient |= 1LL << i;
- }
- }
- return sign * quotient;
- }
- int main(void)
- {
- int n = 36 , m = 12;
- printf(" %d / %d = %d \n", n, m, divide_v1(n, m) );
- printf(" %d / %d = %d \n", n, m, divide_v2(n, m) );
- return 0;
- } // main()
RAW Paste Data
Copied