こちらです

情報工学演習
課題２４
ビットシフトとかけ算
情報 2 年
番
1 月 23 日
名前
【問題 1】ビットシフトを使ったかけ算
下の例を見て，ビット演算の右シフトと左シフトを利用してかけ算を行うプログラムを作成しなさい．
データを 2 倍した値は，データを左に 1 ビットシフトすることで得ることが出来る．例えば，14 を 2 倍し
た値は，左に 1 ビットシフトするとことで作ることが出来る．また，データを 1/2 にした値は，データを右
に 1 ビットシフトすることで作ることが出来る。この様子を下に示す。
10 進数
7
6
5
4
3
2
1
0
10 進数
7
6
5
4
3
2
1
0
14
0
0
0
0
1
1
1
0
14
0
0
0
0
1
1
1
0
X
2
左に 1 ビットシフト
10 進数
7
6
5
4
3
2
1
0
28
0
0
0
1
1
1
0
0
÷
2
右に
1 ビットシフト
10 進数
7
6
5
4
3
2
1
0
7
0
0
0
0
0
1
1
1
これらの性質を利用してシフトと足し算だけで，かけ算をするプログラムを作成しよう．
【問1】かける数が奇数か偶数かを判定する．第 0 ビットが 0 であれば偶数，1 であれば奇数となる。
偶数の例
奇数の例
7
6
5
4
3
2
1
0
0
0
0
1
0
1
10
0
11
0
7
6
5
4
3
2
1
0
0
0
0
0
1
0
1
1
②かける数が奇数の時は，かける数を（偶数＋1）に分解し，分配の法則により偶数のかけ算と足し算に分
解する．足し算は別の変数に加えて記憶しておく．
かけられる数
かける数
「実行例」
a
b
かけ算をします a,b を入力
3 × 5
かける数は奇数
4 13↓
＝
3 × (4 ＋ 1)
答え
4 * 13 = 52
＝
3 × 4
＋ 3
括弧を分解した
③かける数が偶数の時は，かけられる数を 2 倍(1 ビット左にシフト)し，かける数を 1／2 倍（1 ビット右
シフト）する．これにより式全体の値は変わらない。
かけられる数
かける数
a
b
3 × 4
かける数は偶数
＝
3×2 × 4÷2
×2÷2 なので答えは変わらない
＝
6 × 2
④①~③を繰り返し，かける数が 1 になったとき，②で発生した足し算部分の合計を加え，演算を終了する．
かけられる数
かける数
足し算部分（の和）
a
b
t
3 × 5
＝
3 × (4 ＋ 1)
＋
0
＝
3 × 4
＋
3
括弧を分解した
＝
6 × 2
＋
3
＝
12 × 1
＋
3
答え
かけられる数+足し算部分＝12＋3＝15
1
情報工学演習
課題２４
ビットシフトとかけ算
情報 2 年
番
名前
【問 1】問題の理解 1
解説④（前ページ）の例を見て、同じように下の例に対して行いなさい．
(1)
かけられる数
かける数
a
b
3 × 7
足し算部分（の和）
t
0
(2)
かけられる数
かける数
a
b
4 × 15
足し算部分（の和）
0
2
1 月 23 日
情報工学演習
課題２４
ビットシフトとかけ算
情報 2 年
番
1 月 23 日
名前
【問 2】問題理解 2
下の説明文の括弧の中に入る言葉を，選択肢の中から選び書きなさい．
かける数が奇数か偶数かを判定するには，その第 0 ビットに注目し，その値が 0 であれば
いう様に判定します．第 0 ビットを取り出すには
り，1 であれば
を求めます．
この演算には
0x0001 即ち
であ
1 との
という演算子（記号）を用います．
a を左に 1 ビットシフトして，改めてａに代入するには
と書きます．同じように b を右に
1 ビットシフトして改めて b に代入するには
と書きます．
問 1 の最後の実行例を見れば分かるように，この問題の繰り返し条件は，
なります．更に，この繰り返しの中で，
に
が偶数ならば以下の二つの処理をします．
・
を
します．
・
を
します．
奇数ならば，以下の二つの処理をします．
・
を 1 減らします．
・
を
に加えます．
ここでかける数 b が偶数かどうかは，%を使って余りを求めるのではなく，ビット演算を使い第 0 ビット
の値を求めます。b の第 0 ビットを求めるには，
との
if（
より求めます。これを使いプログラムでは，
==
を取ることに
0
）の様に書きます。
(選択肢)
・奇数
・
偶数
･
・
・
＊
・
・a=a<1
・
a=a<<1
・a=>1
・a=a>>1
・b=b<<1
・b=b>>1
・かけられる数ａ
・かける数ｂ
・足し算部分 t
・かけられる数 a が 1 より大きい間
｜
論理和（OR）
&
・
論理積（AND）
・
%
・かける数 b が 1 より大きい間
・足し算部 t が 0 より大きい間
・かける数 b が 1 である間
・左に 1 ビットシフト
・右に 1 ビットシフト
・1
・
b|0
・
b&0
3
・
0
・
b&1
情報工学演習
課題２４
ビットシフトとかけ算
情報 2 年
番
名前
1 月 23 日
【問 3】プログラムの流れ
次のフローチャートの中に入る文を選択肢の中から選び，解答欄に書きなさい．
a,bの読み込み
偽
真
真
B)
かけられる数 a が 1 より大きいか？(繰り返し
条件)
かける数 b が 1 より大きいか？(繰り返し条件)
C)
D)
E)
F)
a,b の記憶，足し算部分（の和）t=0
a=b=0
a を左に 1 ビットシフト
b を右に 1 ビットシフト
G)
H)
I)
J)
t を右に 1 ビットシフト
a を 1 引く
b を 1 引く
a を t に加える
K)
L)
M)
b を t に加える
t を a に加える
t を b に加える
N)
O)
P)
かける数の第 0 ビットが 0 か？
t と a を加えて答とする
a と b を加えて答とする
A)
偽
結果表示
解答欄 (下に自分で図と解答を書きなさい)
4
情報工学演習
課題２４
ビットシフトとかけ算
情報 2 年
番
名前
1 月 23 日
【問 4】プログラム
前ページに書いたフローチャートなどを見ながら残りの部分をプログラムしなさい．タイプするときは，
コメントや空白行を使ってプログラムを分かりやすくしなさい．
かけ算の代わりにビットシフトを使う問題であるから、絶対にかけ算をプログラムの中で実行してはいけ
ない。
#include <stdio.h>
void main( void )
{
int
a,b ,
// a * b
input_a,input_b;
// a,bの記憶用
t=0,
// 足し算部
ans;
「実行例」
かけ算をします a,b を入力してください
4 13↓
答え
4 * 13 = 52
実行例は上記だけでなく、桁の大きなかけ
算がうまくできるか実行し、提出しなさい。
// a,bの入力
// a,bは処理の途中で変化しますから、最後の数式表示が出来ません。そこでこれらを記憶します。
while(
){
//偶数の場合
//奇数
}
//答え計算
ａ
と
t を加える
//数式と答えの表示
}
5

Download Report