怎么使用C++實現兩數相除

這篇文章主要介紹“怎么使用C++實現兩數相除”，在日常操作中，相信很多人在怎么使用C++實現兩數相除問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”怎么使用C++實現兩數相除”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

兩數相除

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

• Both dividend and divisor will be 32-bit signed integers.

• The divisor will never be 0.

• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [?231,  231 ? 1]. For the purpose of this problem, assume that your function returns 231 ? 1 when the division result overflows.

這道題讓我們求兩數相除，而且規定不能用乘法，除法和取余操作，那么這里可以用另一神器位操作 Bit Manipulation，思路是，如果被除數大于或等于除數，則進行如下循環，定義變量t等于除數，定義計數p，當t的兩倍小于等于被除數時，進行如下循環，t擴大一倍，p擴大一倍，然后更新 res 和m。這道題的 OJ 給的一些 test case 非常的討厭，因為輸入的都是 int 型，比如被除數是 -2147483648，在 int 范圍內，當除數是  -1 時，結果就超出了 int 范圍，需要返回 INT_MAX，所以對于這種情況就在開始用 if 判定，將其和除數為0的情況放一起判定，返回 INT_MAX。然后還要根據被除數和除數的正負來確定返回值的正負，這里采用長整型 long 來完成所有的計算，最后返回值乘以符號即可，代碼如下：

解法一：

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        long m = labs(dividend), n = labs(divisor), res = 0;
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
        if (n == 1) return sign == 1 ? m : -m;
        while (m >= n) {
            long t = n, p = 1;
            while (m >= (t << 1)) {
                t <<= 1;
                p <<= 1;
            }
            res += p;
            m -= t;
        }
        return sign == 1 ? res : -res;
    }
};

我們可以通過遞歸的方法來解使上面的解法變得更加簡潔：

解法二：

class Solution {
public:
    int divide(int dividend, int divisor) {
        long m = labs(dividend), n = labs(divisor), res = 0;
        if (m < n) return 0;
        long t = n, p = 1;
        while (m > (t << 1)) {
            t <<= 1;
            p <<= 1;
        }
        res += p + divide(m - t, n);
        if ((dividend < 0) ^ (divisor < 0)) res = -res;
        return res > INT_MAX ? INT_MAX : res;
    }
};

到此，關于“怎么使用C++實現兩數相除”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！