题解 | #牛群的数量计算# 位运算

知识点

位运算

思路

要求实现无加减乘除运算的乘法; 我们可以将一个乘数按位拆解，这样就可以用位运算得到1,2,4,8..倍的数值

之后我们实现无需加减乘除的加法即可

AC Code(C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型 
     * @return int整型
     */
    int multiply(int n, int a) {
        if (!n or !a) return 0;
        int res = 0;
        // 对a二进制分解
        for (int i = 0; i < 32 and a > 0; i ++) {
            if (a >> i & 1) {
                res = sum(res, n << i);
                a -= (1 << i);
            } 
        }
        return res;
    }
    int sum(int a, int b) {
        if(b == 0) return a;
        return sum(a ^ b , (unsigned int)(a & b) << 1);
    }
};