二进制位移乘除法

发布于 2023-12-04  294 次阅读


乘法:

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

除法:

class Solution {
    long long divideHelper(long long dividend, long long divisor) 
    {
        if (dividend < divisor) return 0;

        long long sum = divisor;
        long long multiple = 1;

        while ((sum + sum) <= dividend) 
        {
            sum += sum;
            multiple += multiple;
        }
        return multiple + divideHelper(dividend - sum, divisor);
    }

public:
    int divide(int dividend, int divisor) 
    {
        // 处理特殊情况
        if (divisor == 0) return INT_MAX;
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;

        // 判断符号位
        int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;

        // 取绝对值进行计算
        long long absDividend = llabs(dividend);
        long long absDivisor = llabs(divisor);

        // 递归计算
        long long result = divideHelper(absDividend, absDivisor);

        // 考虑符号位
        result = sign * result;

        // 检查是否溢出
        if (result > INT_MAX || result < INT_MIN) return INT_MAX;

        return static_cast<int>(result);
    }
};