剣指Offer-48.加減乗除しないで加算(C++/Java)

3132 ワード

タイトル:
1つの関数を書いて、2つの整数の和を求めて、関数の体内で+、-、*、/の4つの演算記号を使用してはいけないことを要求します.
分析:
加算を最も原始的な計算方法に還元します.つまり、それぞれ進位と非進位の和を計算し、最後にこの2つの部分を合わせます.私たちは&と<
例えば5+9,5のバイナリは101,9のバイナリは1001であり,まず2つの数の進位,すなわち5&9=1を求め,さらに左に1ビットシフトし,2(0010)が進位であり,その後,異または進位を計算しない和を利用し,101^1001=1100を求め,その後,&和^を進位が0になるまで利用する.
プログラム:
C++
class Solution {
public:
    int Add(int num1, int num2)
    {
        if(num1 == 0)
            return num2;
        if(num2 == 0)
            return num1;
        int carry = 1;
        while(num2 != 0){
            carry = (num1 & num2) << 1;
            num1 = num1 ^ num2;
            num2 = carry;
        }
        return num1;
    }
};

Java
public class Solution {
    public int Add(int num1,int num2) {
        if(num1 == 0)
            return num2;
        if(num2 == 0)
            return num1;
        int carry;
        while(num2 != 0){
            carry = (num1 & num2) << 1;
            num1 = num1 ^ num2;
            num2 = carry;
        }
        return num1;
    }
}