応用情報技術者をpythonとともに学んでいく

応用技術者試験 平成22年 春季 5問目(AP-H22-S-05)

---

流れ図は、シフト演算と加算の繰り返しによって2進整数の乗算を行う手順を表したものである。この流れ図中のa, b の組み合わせとして適切なものはどれか。ここで、乗数と被乗数は符号なしの16ビットであらわされる。X,Y,Zは32ビットのレジスタであり、けた送りに論理シフトを用いる。最下位ビットを第0ビットと記す。

一体何の問題なのか全くわからなかったので、上記プログラミングをpythonで作った。
結論：パソコンの中(2進数)でどのように掛け算が行われているかのプログラミングであった。

下に解説あり。以下プログラムをgoogle Colaboratoryにコピペして使えると思います。一番上のx = とy = をいじると、より理解が深まります。

x = 0b0000000000001101 # 被乗数 13  "0b"は2進数であることを宣言し、それ以降が2進数になる
y = 0b0000000000010100  #乗数 20
print('x=', x,'y=',y)  #いったんx,yの結果を出力に出したかったので記述
Z = 0b0000000000000000 #問題にあるようZに0を入れる
i = 1　　　　　　　　　　#問題にあるようiに1を入れる

while i < 16:          #16回の繰り返し
  yif = y & 0b0000000000000001　#「Yの第0ビットが1だったら」の部分を表現。論理和1*1=1,1*0=0にしてあぶりだしている。参考はhttps://yottagin.com/?p=5122 を見た
  print('yif=' , bin(yif))　#いったん論理和の結果を出す
  if yif > 0:          #論理和が1だったら
   print('加算')
   Z = Z + x           #加算する
  else: 
      print('飛ばし')   #論理和が0だったら何もしない
  print('Z =' ,Z)
  x = x << 1            #問題にあるようにXを左シフト
  print('x =' ,bin(x),x)
  y = y >> 1            #問題にあるようにXを右シフト
  print('y =' ,bin(y),x)
  i += 1                #iに1を加算以降26回繰り返し

以下は出力結果であり、プログラムではないです
x= 13 y= 20
------------------------------------------
yif= 0b0
飛ばし
Z = 0
x(2進数) = 0b11010 x(10進数) = 26
y(2進数) = 0b1010 y(10進数) = 26

yif= 0b0
飛ばし
Z = 0
x(2進数) = 0b110100 x(10進数) = 52
y(2進数) = 0b101 y(10進数) = 52

yif= 0b1
加算
Z = 52
x(2進数) = 0b1101000 x(10進数) = 104
y(2進数) = 0b10 y(10進数) = 104

yif= 0b0
飛ばし
Z = 52
x(2進数) = 0b11010000 x(10進数) = 208
y(2進数) = 0b1 y(10進数) = 208

yif= 0b1
加算
Z = 260
x(2進数) = 0b110100000 x(10進数) = 416
y(2進数) = 0b0 y(10進数) = 416

yif= 0b0
飛ばし
Z = 260
x(2進数) = 0b1101000000 x(10進数) = 832
y(2進数) = 0b0 y(10進数) = 832

yif= 0b0
飛ばし
Z = 260
x(2進数) = 0b11010000000 x(10進数) = 1664
y(2進数) = 0b0 y(10進数) = 1664

yif= 0b0
飛ばし
Z = 260
x(2進数) = 0b110100000000 x(10進数) = 3328
y(2進数) = 0b0 y(10進数) = 3328

yif= 0b0
飛ばし
Z = 260
x(2進数) = 0b1101000000000 x(10進数) = 6656
y(2進数) = 0b0 y(10進数) = 6656

yif= 0b0
飛ばし
Z = 260
x(2進数) = 0b11010000000000 x(10進数) = 13312
y(2進数) = 0b0 y(10進数) = 13312

yif= 0b0
飛ばし
Z = 260
x(2進数) = 0b110100000000000 x(10進数) = 26624
y(2進数) = 0b0 y(10進数) = 26624

yif= 0b0
飛ばし
Z = 260
x(2進数) = 0b1101000000000000 x(10進数) = 53248
y(2進数) = 0b0 y(10進数) = 53248

yif= 0b0
飛ばし
Z = 260
x(2進数) = 0b11010000000000000 x(10進数) = 106496
y(2進数) = 0b0 y(10進数) = 106496

yif= 0b0
飛ばし
Z = 260
x(2進数) = 0b110100000000000000 x(10進数) = 212992
y(2進数) = 0b0 y(10進数) = 212992

yif= 0b0
飛ばし
Z = 260
x(2進数) = 0b1101000000000000000 x(10進数) = 425984
y(2進数) = 0b0 y(10進数) = 425984

【解説】
xとyをそれぞれ2進数展開する
xは1101(13)である。
yの一番右は1010(0)　であるので今回は何もしない。
yの右から2番目 101(0)0も0であるので何もしない。
yの右から3番目は10(1)00で1であるので以下アクションをする。
アクション：右から三番目ということはxで言うところの左に2回シフトした数字である。10進数で2回左にシフトというとつまり10^2倍(100倍)することである。つまり2進数で2回左にシフトするのは2^2倍(4倍)することである。
xは13であるので 13×4=52 となるので、それをZに足す
　　現在Z = 52

同じようにyは右から5番目(1)0100で1であるので、xはさらに左に2回シフト(2倍の2倍)して 52 * 4 = 208 をZに加える
　　Z = 52 + 208 = 260
この結果が 13 × 20 = 260 と同じ事である。

2進数での掛け算をプログラムでやるとこうなるのか、と勉強になる1問でした。