せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【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

 
べき乗もビット演算で行ってる
べき算を掛け算に分解するから、上記のメソッドを利用できる。
 
なるほど。