【C++】位運算實作加減乘除

近日複習劍指offer，看到了當時寫第65題題實作了位運算的加減乘除法，特此記錄

1.加法

• 位的異或運算跟求"和"的結果一緻：

  異或 1^1=0 1^0=1 0^0=0

  求和 1+1=0 1+0=1 0+0=0

• 位的與運算後<<1的結果跟求"進位"的結果一緻：

  位與 1&1=1 1&0=0 0&0=0

  進位 1+1=1 1+0=0 0+0=0

• 而二進制加法分為三步：（如1001+1011，9+11=20）

  ① 各位相加但不計進位，得到00010；（該結果即為1001與1011的^結果）

  ② 記下所被略去的進位，得到10010；（該結果即為1001與1011的&結果<<1後的結果）

  ③ 将①與②相加，得到10100，即為20

  但是由于無法使用加法，是以最後的兩個10兩者無法直接相加得到100，需要通過循環重複①與②步驟來實作加法

  （循環終止的條件與遞歸的終止條件相同，都是當②計算所得到的進位為0即停止計算）

• 是以，可以将異或的值作為目前的值s，而當進位c存在時，将其前移一位，用于和之後的s繼續進行^與&運算

//1.兩種加法運算，運作時間：3ms，占用記憶體：468k
	int Add(int num1, int num2)
	{
		int sum, carry;
		while (num2 != 0)
		{
			//sum是和，而carry是進位，sum表示計算的①，carry表示計算的②，不斷地進行①與②，直到②為0
			sum = num1^num2;
			carry = (num1&num2) << 1;
			num1 = sum;
			num2 = carry;
		}
		return num1;
	}

	int Add2(int num1, int num2)
	{
		if (num2 == 0)
			return num1;
		int sum = num1^num2;
		int carry = (num1&num2) << 1;
		Add2(sum, carry);
	}
           

2.減法

• 減法沒啥好說的，注意負數是正數的取反後+1

//2.一種減法運算
	int Negtive(int num1, int num2)
	{
		//減法即num1+(-num2),注意計算機用補碼存的，是以-num2 = ~(num2 - 1) = ~num2 + 1 = Add(~num2,1)
		return Add(num1, Add(~num2, 1));
	}
           

3.乘法

• 首先将乘數與被乘數弄為正數，最後再添加符号，而實作過程按照國小乘法算法實施

//3.一種乘法運算（首先将乘數與被乘數弄為正數，最後再添加符号，而實作過程按照國小乘法算法實施）
	int Multiply(int num1, int num2)
	{
		if (num2 == 0 || num1 == 0)
			return 0;
		//先将被乘數與乘數全部弄為正數
		int multiplicand = (num1 < 0) ? (Add(~num1, 1)) : num1;
		int multiplier = (num2 < 0) ? (Add(~num2, 1)) : num2;
		int multip = 0;
		while (multiplier > 0)
		{
			//如果最後一位是1，則進行加運算
			if (multiplier & 0x1 == 1)
				multip = Add(multip, multiplicand);
			//無論是否進行了加運算，都将被乘數左移一位，乘數右移一位
			multiplicand <<= 1;
			multiplier >>= 1;
		}
		//恢複符号，num1^num2為負值時表示兩者異号，相乘必為負值
		//（注意<優先級高于^，記得加括号）
		if ((num1^num2) < 0)
			multip = Add(~multip, 1);
		return multip;
	}
           

4.除法

• 計算機是一個二進制的世界，所有的int型資料都可以用[20, 21, …, 231]這樣一組基來表示（int型最高31位）。不難想到用除數的231, 230, …, 22, 21, 20倍嘗試去減被除數，

  如果減得動，則把相應的倍數加到商中；如果減不動，則依次嘗試更小的倍數。這樣就可以快速逼近最終的結果。

• 在此特别提醒，對于C++的除法來說，其原則在于使商盡量去乘除數後去比對被除數（其根兩數的同符号與異符号時均有不同）

//4.一種除法運算
	int Divide(int num1, int num2)
	{
		if (num1 == 0)
			return 0;
		if (num2 == 0)
			return 0;
			//throw new exception("error");
		//先将被除數與除數全部弄為正數
		int dividend = (num1 < 0) ? (Add(~num1, 1)) : num1;
		int divider = (num2 < 0) ? (Add(~num2, 1)) : num2;
		int quotient = 0;	//商
		int remainder = 0;	//餘數
		//周遊31到0，實作除數的快速運算
		for (int i = 31; i >= 0; i--)
		{
			//注意這裡的dividend與divider比較，是将dividend右移i位而不是将divider左移i位
			//目的在于避免divider左移i位後有些資料丢幀
			if ((dividend >> i) >= divider)
			{
				//如果(dividend >> i) >= divider，表示dividend除divide的值大于1<<i，則将1左移i位并加入到商中
				//此時表示從dividend中減去了1<<i個divide，是以dividend的值也跟着更新
				quotient = Add(quotient, 1 << i);
				dividend = Negtive(dividend, divider << i);
			}
		}
		//恢複商符号，符号相反時，商必為負數，否則為正數
		//恢複餘數符号，注意餘數是根據最後被減沒了的dividend實作的，而其符号根據被除數與除數的符号性相比對
		if ((num1^num2) < 0)
		{
			quotient = Add(~quotient, 1);
			if (num1 < 0)
				remainder = Add(~dividend, 1);
			else
				remainder = dividend;
		}
		else
			//當符号相同時，根據任一數的符号即可确定餘數符号
			remainder = (num1 < 0) ? (Add(~dividend, 1)) : (dividend);
		cout << quotient << endl;
		cout << remainder << endl;
		return quotient;
	}