【離散数学】シフト演算

シフト演算

シフト演算は、桁を左右にずらすことでべき乗の計算をする方法。ひいては乗算や除算を行うことができる。

2進数のシフト演算

• 左にnビットシフト：元の数値の2ⁿ倍になる
• 右にnビットシフト：元の数値の2^-n倍になる

論理シフトと算術シフト

シフトには論理シフトと算術シフトがあり、違いは左端の１ビットを符号として扱うかどうか。論理シフトは全ビットを対象とするので負の数を扱うことはできないが、算術シフトは符号ビットを固定するので負の数を扱える。

論理シフト

論理右シフト

• 2進数の全ビットをそのまま右へ移動する。
• 空いた左端のビットには0が入る。

論理左シフト

• 2進数の全びっとをそのまま左へ移動する。
• 空いた右端のビットには0が入る。

算術シフト

算術右シフト

• 符号ビット以外の全てのビットをそのまま右へ移動する。
• 左の空いたビットには符号ビットと同じ値が入る。

算術左シフト

• 符号ビット以外の全てのビットをそのまま左へ移動する。
• 空いた右端のビットには0が入る。

シフト演算と乗除算

例１：10進数の演算式7/32の結果を2進数で表す

• 10進数32は2⁵で表せるので、元の数を5ビット右シフトすれば求める結果になる。

例２：2進数で表された正の整数xを10倍する。ただし、桁あふれは起こらないものとする。

• 元の値が整数であれば、必ず2ⁿの和に分解できる。
  • 12倍 = 8倍+4倍 = 2³ + 2²
  • 18倍 = (8倍+1倍)*2倍 = (2³ + 2⁰)*2¹
  • 20倍 = (4倍+1倍)*4倍 = (2² + 2⁰)*2²