【九日集训】第一天打卡

371. 两整数之和 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    int getSum(int a, int b) {
        /**
        本位相加：0+0=0  0+1=1  1+0=1  1+1=0（进位是1）
        本位： a^b
        进位： (a&b)<<1
        4     0100
        5     0101
        -------------
        a^b   0001   
        (a&b)<<1 1000
        ---------------
        a^b    1001
        (a&b)<<1 0000
        -------------- done
        */
        while(b != 0)
        {
            unsigned int carry = (unsigned)(a&b)<<1;
            a ^= b;
            b = carry;
        }
        return a;
    }
};

面试题 17.01. 不用加号的加法 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    int add(int a, int b) {
        while(b != 0)
        {
            unsigned int carry = (unsigned)(a&b)<<1;
            a^=b;
            b=carry;
        }
        return a;
    }
};

剑指 Offer 65. 不用加减乘除做加法 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    int add(int a, int b) {
        while(b)
        {
            unsigned int c = (unsigned)(a&b)<<1;
            a^=b;
            b=c;
        }
        return a;
    }
};

面试题 08.05. 递归乘法 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    int multiply(int A, int B) {
        /*
        B偶数： A*B = A*B/2 + A*B/2
        B奇数： A*B = A*B/2 + A*B/2 + A

        1 ^ 1 = 0
        1 ^ 0 = 1
        1 & 1 = 1
        1 & 0 = 0
        
        */
        if(B==0)
            return 0;
        if(B==1)
            return A;
        
        int ret = multiply(A, B>>1)<<1;
        if(B&1 == 1)
            ret += A;

        return ret;
    }
};