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

牛群的数量计算

https://www.nowcoder.com/practice/dfafaa65a55040b3a4b65418db68949d?tpId=354&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D354

一、知识点:

二进制运算

二、文字分析:

代码的时间复杂度为O(log(n)),空间复杂度为O(log(n))。

在这个算法中,我们使用了一个辅助方法addBits(int bit1, int bit2, int carry)来实现两个二进制位的相加操作,而multiply(int n, int a)方法中没有使用加法运算。

三、编程语言:

java

四、正确代码:

public class Solution {
    /**
     * 计算所有牧场的牛的数量总和
     * @param n 牧场的数量
     * @param a 每个牧场的牛的数量
     * @return 所有牧场的牛的数量总和
     */
    public int multiply(int n, int a) {
        int sum = 0;
        int carry = 0;  // 进位
        while (n != 0) {
            if ((n & 1) == 1) {
                sum = addBits(sum, a, carry);  // 将 n 和 a 的对应位相加
            }
            n = n >>> 1;  // 向右移位,相当于 n 除以 2
            a = a << 1;   // 向左移位,相当于 a 乘以 2
        }
        return sum;
    }
    
    // 实现两个二进制位的相加,返回相加结果
    private int addBits(int bit1, int bit2, int carry) {
        if (bit2 == 0) {
            return bit1 ^ carry;  // 无进位相加
        }
        int sum = bit1 ^ bit2 ^ carry;        // 无进位相加
        int newCarry = (bit1 & bit2) | (bit1 & carry) | (bit2 & carry);  // 计算新的进位
        return addBits(sum, newCarry << 1, 0); // 递归调用,将新的进位和无进位相加的结果相加
    }
}
全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务