20230514基本情報技術者試験的な備忘録 2017年（平成29年） 春午前 問5 アルゴリズム
アルゴリズム素人です。
基本情報技術者試験素人です。
以下違いだらけです。自分用メモ。（本格的な解説ではありません。）
参考問題：
基本情報技術者試験 午後 2017年（平成29年） 春午前 問5 アルゴリズム
問題の画像は、IPA様、過去問道場様より引用しました。
（問題あれば削除いたします。）
この問題の答えは、「ア」です。
aの空欄・・・ Yの第0ビット
bの空欄・・・ Xを１ビット左シフト、Yを１ビット右シフト
過去問道場様の解説を読む。それと、過去問道場様のページに載っていたプログラム（javascript）をやってみる。(ありがたいです。)
それでもなんとなくしっくりこなくて記事を書いている始末・・・。
基本は、「論理シフト」。
２進数で、
１ビット左シフトすると２倍
１ビット右シフトすると１/２倍。（これらがキホン）
で、１０進数「３×３」を考えてみる。
（以下、細かくは書きません。メモ）
２進数だと、それぞれ
X 0011
Y 0011
になる。（桁数は割愛）
まず、回答aの 「Yの第0ビット：１」 のところの意味
Ｙが、００１「１」だったら、下記の
（Ｚ＋Ｘ） → Ｚ
をすることになる。（加算）
で、
Ｘ ００１１（全体３）
Ｙ ０００「１」（１なら足すぞ）
と考え、Ｚが３になる。（Ｘ（全体３）がＹ（１）で該当なのでＺ（元０）に入れる）
で、次に、回答bの 「Xを１ビット左シフト、Yを１ビット右シフト」 のところの意味
後半の「Yを１ビット右シフト」は、ループして回答aの 「Yの第0ビット：１」を２桁目に使用するための処理。
Ｙ ００「１」１→０００「１」（１なら足すぞ）
前半の「Xを１ビット左シフト」は、
Ｘ ００１１→０１１０（全体６）になり、
計算
Ｘ ０１１０（全体６）
Ｙ ０００「１」（１なら足すぞ）
と考え、Ｚが合計９になる。（Ｘ（全体６）がＹ（１）で該当なのでＺ（元３）に合算）
でも、何で、「Xを１ビット左シフト」するの？ということになってしまう。
結果から言えば、計算上「Yを１ビット右シフト」したからということなのだが、納得しにくい。
＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋
アルゴリズムで考えなければ単純で、
Ｘ ００１１
Ｙ ００１１
の掛け算の場合、
Ｘ ００１１
Ｙ ００１「１」←１桁目の１を処理
Ｘは、全体３。で１（２進数の１ビット目の重み）を掛ける。で３
Ｘ ００１１
Ｙ ００「１」１←２桁目の１を処理
Ｘは、全体３。で２（２進数の２ビットの重み）を掛ける。で６
で３＋６ ＝９
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
４×３でも同じ
Ｘ ０１００
Ｙ ００１１
Ｘ ０１００
Ｙ ００１「１」←１桁目の１を処理
Ｘは、全体４。で１（２進数の１ビット目の重み）を掛ける。で４
Ｘ ０１００
Ｙ ００「１」１←２桁目の１を処理
Ｘは、全体４。で２（２進数の１ビット目の重み）を掛ける。で８
で４＋８ ＝１２
なんとなくそんな感じで納得。？？
