递归乘法(位操作)

题目要求吝啬地递归，那就是递归的深度要小一些。肯定不能使用加法，这里用到位操作。也就是俄罗斯农民乘法。

class Solution { public: int multiply(int A, int B){ if(B==0) return 0; if(B&1){ return A+multiply(A<<1,B>>1); } else return multiply(A<<1,B>>1); } };

时间复杂度分析，每次让B<<1，也就是B/2，那么时间复杂度就是O(logB),在c++中，int为32位，那么就是常数级的O(32)=O(1)