【Ruby】【アルゴリズム】加算回路を使った足し算

アルゴリズムを理解するために、この本を読んでいる。

この中で、加算回路の解説があって簡単そうなので実装してみた。

罠でした。
思ったより難しかったよー。。

足し算って、

100 + 1

とあったとき、1の桁は0と1だから、当然右側から計算していくけれども
右端というのは、配列化した時の1番大きいキーの値。

数値を配列化して、最大キーから逆順に計算しないといけない。

となると、

100 + 1

は

100 + 001

と書き直す必要がある。

作ったコード

def _and(a,b)
  return 0 if a == 0 and b == 0
  return 0 if a == 0 and b == 1
  return 0 if a == 1 and b == 0
  return 1 if a == 1 and b == 1
end
def _or(a,b)
  return 0 if a == 0 and b == 0
  return 1 if a == 0 and b == 1
  return 1 if a == 1 and b == 0
  return 1 if a == 1 and b == 1
end
def _xor(a,b)
  return 0 if a == 0 and b == 0
  return 1 if a == 0 and b == 1
  return 1 if a == 1 and b == 0
  return 0 if a == 1 and b == 1
end
def _sum(a, b, kuriagari)
  answer = {}
  answer[:result] = _xor(kuriagari, _xor(a, b))
  answer[:kuriagari] = _or(_and(kuriagari, _xor(a,b)),_and(a,b))
  answer
end
def sum(int1, int2)
  max = [int1.to_s.length, int2.to_s.length].max
  st1 = "%0#{max}d" %int1
  st2 = "%0#{max}d" %int2
  arr1 = st1.split("")
  arr2 = st2.split("")
  arr1.map! {|x| x.to_i}
  arr2.map! {|x| x.to_i}
  kuriagari= []
  kuriagari[max - 1] = 0
  result = []
  i = max - 1
  while i >= 0
    if i == 0 then
      result[i] = _sum(arr1[i], arr2[i], kuriagari[i])[:result]
      result.unshift _sum(arr1[i], arr2[i], kuriagari[i])[:kuriagari]
    else
      result[i] = _sum(arr1[i], arr2[i], kuriagari[i])[:result]
      kuriagari[i - 1] = _sum(arr1[i], arr2[i], kuriagari[i])[:kuriagari]
    end
    i -= 1
  end
  result.join()
end

p sum(110, 11)

■実行結果