プログラマー面接100題の3:いいえ+、-、×、÷数字演算子を加算する

テーマ:1つの関数を書いて、2つの整数の和を求めて、関数の体内で＋、－、×、÷.
分析:これはまた発散思考を考察する興味深いテーマです.私たちが慣れているものが制限されているとき、どのように通常を突破して考えるかが、この問題を解決する鍵です.
この問題を見て、私の第一反応は愚かな目で、4つの演算はすべて使うことができなくて、それではまた何を使うことができますか?しかし、問題はいつも解決しなければならないので、考えを開いていろいろな可能性を考えるしかありません.まず、5+17=22という結果をどのように得たのかを分析することができます.実際、私たちは3つのステップに分けることができます:第1のステップは皆さんが加算して進位しないことだけをして、この時加算の結果は12(個の桁数の5と7が加算して進位しないのは2で、10の桁数の0と1が加算した結果は1です);第2のステップは進位して、5+7の中で進位があって、進位の値は10です;第3のステップは前の2つの結果を加算して、12+10の結果は22で、ちょうど5+17=22です.
前に私たちは、2つの数と4つの演算を求めても使えないと思っていましたが、何を使うことができますか?そうですね.何が使えますか.数字を演算するには,四則演算のほかにビット演算しか残っていない.ビット演算はバイナリに対して行われるので,バイナリで前の3ステップ戦略がバイナリに対しても役に立つかどうかを分析する.
5のバイナリは101,17のバイナリ10001です.やはり計算を3つのステップに分けてみましょう.最初のステップは皆さんが加算しても進位は計算されません.結果は10100(最後の桁の2つの数はいずれも1で、加算結果はバイナリの10である.このステップはキャリーを含まないので結果は0である);第2ステップはキャリーを記す.この例では最後の桁が加算されたときにのみ1つのキャリーが生成され、結果はバイナリの10である;第3ステップは前の2ステップの結果を加算し、得られた結果は10110で、ちょうど22である.このことから、3ステップの戦略対バイナリも役に立ちます.
次に,バイナリ上の加算をビット演算に置き換えてみた.最初のステップは、キャリーを考慮せずに、各ビットを加算します.0プラス0と1プラス1の結果はいずれも0で、0プラス1と1プラス0の結果はいずれも1です.これは異或の結果と同じであることに気づくことができる.異種または0、1および1異種の結果は0であり、0および1、1および0の異種または結果は1である.次に、第2ステップのキャリーを考えると、0に0、0に1、1に0を加えると、いずれもキャリーが発生せず、1に1を加えると、前方に1つのキャリーが発生する.このとき,2つの数がまずビットと演算を行い,それから左に1つ移動することを想像できる.2つの数だけが1の場合,ビットと得られた結果は1であり,残りは0である.3ステップ目は、前の2つのステップの結果を加算します.関数AddWithoutArithmeticを定義すると、3番目のステップは、前の2つのステップの結果を入力して自分を再帰的に呼び出すことに相当します.
これらの分析があれば、以下のコードを書くのは難しくありません.

int AddWithoutArithmetic(int num1, int num2)
{
	if(num2 == 0)
		return num1;
	int sum = num1 ^ num2;   //    
	int carry = (num1 & num2) << 1;     // 0 0、0 1、1 0  ，       ，  1 1 ，         。           ，         。
	return AddWithoutArithmetic(sum, carry);
}

zhedahhtから転載blog.163.com