算術演算子なしで加算の実装

”世界で戦うプログラミング力を鍛える150問”から問題を解いた.

算術演算子を使用せずに加算を実装する.

方針

ビット演算を考える. 数の和は各桁の繰り上がりなしの和(sum)とその繰り上がり(carry)の和で表せる. 加算の計算の中に加算が現れるため,繰り上がりがなくなるまで再帰が必要.

加算の関数をaddとするとadd関数の実装は以下の手順になる.

  1. 各桁のXORを取る(sum)

  2. 各桁のANDの左シフトを取る(carry)

  3. sumとcarryでadd関数を再帰する

コード

pythonで作成した例を示す.

解いてみて

計算機の講義で出てきた加算器の話とほとんど同じだった.

演算子の再実装をしろと面接で言ってくる企業がいくつかあるそうな. 他の演算子も試してみたい.

広告を非表示にする