応用情報技術者を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問でした。
この記事が気に入ったらサポートをしてみませんか?