两个数相乘

/*
问题描述：计算两个无符号整数相乘的结果，不能使用加法，乘法，++等操作符
来源：网易算法课
作者：syt
日期：2017-9-17
思路：两个数相乘，不能使用乘法，一般转化到二进制的形态下进行操作，
两个二进制数相乘，可以转化为两个二进制数移位相加，由于不能使用加法，只要解决
不使用加法实现两个二进制数相加即可。

*/

#include <iostream>
#include <stack>

using namespace std;

//计算r中1所在的位数
int shift(int r)
{
 int p = 0;
 while (r > 0)
 {
  if ((r & 1) > 0)
  {
   return p;
  }
  r = r >> 1;
  p++;
 }
 return p;
}

//两个二进制数相加
int binaryAdd(int x, int y)
{
 int result = 0;
 int advance = 0;//进位
 int r = 1;//当前计算的位数

 while (x > 0 || y > 0)
 {
  int i = x & 1;
  int j = y & 1;

  x = x >> 1;
  y = y >> 1;

  int b = i^j;

  if (b > 0)
  {
   if (advance != 0)
   {
    b = 0;
   }
  }
  if (b == 0)
  {
   if ((i&j) > 0)
   {
    if (advance != 0)
    {
     b = 1;
    }
    else
    {
     advance = 1;
    }

   }
   else
   {
    if (advance != 0)
    {
     b = 1;
     advance = 0;
    }
   }
  }

  if (b > 0)
  {
   b = b << shift(r);
   result = result | b;
  }
  r = r << 1;
 }
 if (advance > 0)
 {
  result = result | (advance << shift(r));
 }
 return result;

}


//两个数相乘
int binaryMultiply(int a, int b)
{
 stack<int> mstack;
 int i = 0;

 //将ａ转化成二进制
 while (b > 0)
 {
  if ((b & 1) > 0)
  {
   mstack.push(a << i);
  }
  else
  {
   mstack.push(0);
  }

  b = b >> 1;
  i++;
 }

 while (mstack.size() > 1)
 {
  int x = mstack.top();
  mstack.pop();
  int y = mstack.top();
  mstack.pop();
  int z = binaryAdd(x, y);
  mstack.push(z);
 }

 int result = mstack.top();
 mstack.pop();

 return result;

}