View Single Post
Old 10-11-2012, 01:08 AM   #12
Claxon
Senior Member

Activity Longevity
0/20 18/20
Today Posts
0/11 ssssss345
Location: London
Default Re: C++ Coding Challenges

Quote:
Originally Posted by CY5 View Post
/*"Write a C function that multiplies an input integer by 5 and returns the result. The function must not use the multiplication operator. Optimize for speed."*/
Another faster (although slightly more difficult to read) way would be to use bit-shifting.If you don't know what that means, it's where you move the binary bits up or down by a certain amount.

eg.
In Binary:
0000 0110 = 6

If we bit shift left by 1 bit we get this:
0000 1100 = 12

So shifting by 1 will double the number. Shifting by 2 will multiply it by 4, and so on. The bonus is that bit-shifting is very fast. In your case, multiplying by 5 there is only a very little difference but say you were to multiply by 50 using the same techniques, the bit shifting one is much faster.

This is my version of your code:

Code:
#include <iostream>
#include <time.h>

using namespace std;

int add(int);
int shift(int);

double diffclock(clock_t clock1,clock_t clock2)
{
    double diffticks=clock1-clock2;
    double diffms=(diffticks*1000)/CLOCKS_PER_SEC;
    return diffms;
} 

int main()
{
    bool running = true;
    while(running)
    {
        int a;

        cout<<"Enter no (0 to exit):";
        cin>>a;

        if(a == 0)
            running = false;
        else
        {
            // Use a loop so that we can time the results
            const int loops = 1000000;
            int res = -1; 
            int i=0;

            //-----------------
            // Using Addition
            clock_t begin=clock();
            for(i=0; i<loops; ++i)
            {
                res = add(a);
            }
            clock_t end=clock();
            cout << "Old Version Time elapsed: " << double(diffclock(end,begin)) << " ms     Result:" << res << endl;

            //---------------------
            // Using Bit-shifting 
            begin=clock();
            for(i=0; i<loops; ++i)
            {
                res = shift(a);
            }
            end=clock();
            cout << "New Version Time elapsed: " << double(diffclock(end,begin)) << " ms     Result:" << res << endl;
        }
    }
    return 0;
}

int add(int a)
{
    a=a+a+a+a+a;
    return a;
}

int shift(int a)
{
    return (a << 2) + a;
}
Of course, the minute you build in Release mode instead of Debug mode, the compiler will optimize all of this out anyway!
Claxon is offline