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

使用位运算实现乘法即可!

分别采用累加(递归实现加法),模拟(迭代实现加法)

累加实现乘法

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a 牧场 
     * @param b 牛 
     * @return 乘积
     */
    public int multiply (int a, int b) {
        // write code here
        //取绝对值//负数取反+1
        int multiplicand = a<0?add(~a,1):a;
        int multiplier = b<0?add(~b,1):b;
        int product = 0;
        int count=0;
        // 累加计算
        while(count<multiplier){
            product=add(product,multiplicand);
            count = add(count,1);
        }
        // 判断符号
        if((a^b)<0){
            product=add(~product,1);
        }
        return product;
    }
  //递归写法
    private int add(int a,int b){
        if(b==0)return a;
        int sum = a^b;
        int carry = (a&b)<<1;
        return add(sum,carry);
    }
}

模拟手算二进制乘法

(1) 判断乘数是否为0，为0跳转至步骤(4)

(2) 将乘数与1作与运算，确定末尾位为1还是为0，如果为1，则相加数为当前被乘数；如果为0，则相加数为0；将相加数加到最终结果中；

(3) 被乘数左移一位，乘数右移一位；回到步骤(1)

(4) 确定符号位，输出结果；

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a 牧场 
     * @param b 牛 
     * @return 乘积
     */
    public int multiply (int a, int b) {
        //将乘数和被乘数都取绝对值　
        int multiplicand = a < 0 ? add(~a, 1) : a;
        int multiplier = b < 0 ? add(~b, 1) : b;
        //计算绝对值的乘积　　
        int product = 0;
        while (multiplier > 0) {
            if ((multiplier & 0x1) > 0) { // 每次考察乘数的最后一位
                product = add(product, multiplicand);
            }// 每运算一次，被乘数要左移一位　　　　
            multiplicand = multiplicand <<1;
            // 每运算一次，乘数要右移一位（可对照上图理解）　　
            multiplier = multiplier >>1;
        }
        //计算乘积的符号　　
        if ((a ^ b) < 0) {
            product = add(~product, 1);
        }
        return product;
    }
    // 迭代写法
    private int add(int num1, int num2) {
        int sum = num1 ^ num2;
        int carry = (num1 & num2) << 1;
        while (carry != 0) {
            int a = sum;
            int b = carry;
            sum = a ^ b;
            carry = (a & b) << 1;
        }
        return sum;
    }
}