There is an interesting way to multiply two positive integer values without using " * " operator and using binary shift operator. The complexity of the program will depends on the number of bits in the binary representation of the multiplier value.

The naive approach:

We can repeatedly add the value of multiplicand to a temporary variable, addition should be taken place until the addition operation is applied as the numerical value of the multiplier value. The time complexity of this program will depends on the value of multiplier O(n).

Sample program based on the above approach.

#include <iostream>

using namespace std;

int main()
{
        int a, b, i, tmp = 0;
        cout << "Enter two integers to be multiplied : ";
        cin >> a >> b;

        for(i = 0; i < b; i++)
                tmp += a;

        cout << "Output " << a << " * " << b << " = " << tmp << endl;
        return 0;
}

Output of the above program

Enter two integers to be multiplied : 4 5
Output 4 * 5 = 20

A better approach:

Using the AND operator we are going to find the least significant bit in the multiplier by taking the AND operation with 1. If the LSB(left significant bit) of multiplier is 1 then we are going to add the value of multiplicand to a temporary variable, in case of 0 we skip the addition part. In each iteration we are applying left shift operation on multiplier and right shift operation on multiplicand by 1. When the value of multiplier is 0. We have the product of the integers with us. Time complexity of the above program will depends upon the number of bits in the binary representation of multiplier.

Sample program for the above approach

#include <iostream>
#include <stack>

using namespace std;

int main()
{
        int a, b, result = 0;
        stack<int> st; //using stack for the proof of the program.

        cout << "Enter two integers to be multiplied : ";
        cin >> a >> b;
        int tmp = 0;
        int t1 = a;
        int t2 = b;

        while ( b != 0) {
                if ( (b&1) == 1) {
                        result += a;
                        st.push(tmp);
                }
                tmp++;
                a <<= 1;
                b >>= 1;
        }

        cout << "Output " << t1 << " * " << t2 << " = " << result << endl;

        //for printing the format in which shift has been applied..
        //you can comment this part if you don't want it in your solution.. 
        while(!st.empty()) {
                cout << "(" << t1 << "<<" << st.top() << ")";
                        st.pop();
                        if (!st.empty()) {
                                cout << " + ";
                        }
        }
        cout << endl;

        return 0;
}

Output of the above program

Enter two integers to be multiplied : 4 5
Output 4 * 5 = 20
(4<<2) + (4<<0)

Corrections and suggestions are welcomed. :)