【Ruby】【アルゴリズム】ビット演算。掛け算しないで掛け算する。
掛け算・べき乗をビット演算で行っているサイトがあったので勉強。
掛け算を一回もしない掛け算
def shift_multi(x, y) m = 0 while x != 1 if x.even? y = (y << 1) # * 2 x = (x >> 1) # / 2 else m += y x -= 1 end end y += m end p shift_multi(15,3)
奇数の場合は足し算に分解か。
■実行イメージ
15 * 3 14 * 3 + 3 7 * 6 + 3 6 * 6 + 3 + 6 3 * 12 + 3 + 6 2 * 12 + 3 + 6 + 12 1 * 24 + 3 + 6 + 12 24 + 3 + 6 + 12
べき乗もビット演算で行ってる
べき算を掛け算に分解するから、上記のメソッドを利用できる。
なるほど。