1. 題目

遞歸乘法。 寫一個遞歸函數(shù)，不使用 * 運算符， 實現(xiàn)兩個正整數(shù)的相乘。
可以使用加號、減號、位移，但要吝嗇一些。

示例1:輸入：A = 1, B = 10輸出：10示例2:輸入：A = 3, B = 4輸出：12提示: 保證乘法范圍不會溢出

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/recursive-mulitply-lcci
著作權歸領扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 右移1位 == 除以2
• 左移1位 == 乘以2

2.1 遞歸

class Solution { public:int multiply(int A, int B) {if(A < B)A^=B^=A^=B;//swap大的在前，少遞歸幾次if(B==1)return A;if((B&1)==0)//B是偶數(shù)return multiply(A,B>>1)<<1;elsereturn A + (multiply(A,B>>1)<<1);} };

2.2 循環(huán)

class Solution { public:int multiply(int A, int B) {int i = 0, ans = 0;if(A < B)A^=B^=A^=B;//swap大的在前while(B)//把B分解成2進制數(shù)，對每一位乘以A{if((B&1)==1)//該位為1(1,2,4,8,16)ans += A<<i;//移動0,1,2,3,4位B >>= 1;//B的每位移到最右 & 1來判斷i++;}return ans;} };

總結

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 08.05. 递归乘法（位运算）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。