離散数学 (全109問中59問目)
No.59
数値を2進数で表すレジスタがある。このレジスタに格納されている正の整数xを10倍する操作はどれか。ここで，シフトによるけたあふれは，起こらないものとする。
出典：平成20年春期 問4
- xを2ビット左にシフトした値にxを加算し，更に1ビット左にシフトする。
- xを2ビット左にシフトした値にxを加算し，更に2ビット左にシフトする。
- xを3ビット左にシフトした値と，xを2ビット左にシフトした値を加算する。
- xを3ビット左にシフトした値にxを加算し，更に1ビット左にシフトする。
- [出題歴]
- 基本情報技術者 H29秋期 問1
- ソフトウェア開発技術者 H17春期 問1
分類
テクノロジ系 » 基礎理論 » 離散数学
正解
ア
解説
ビットシフトを使用した乗算に関する問題です。
2進数のビット列は、左にnビットシフトすると元の値と比べて「2n倍」、右にnビットシフトすると「1／2n倍（2-n倍）」になるという性質があります。
これを踏まえて各選択肢が何倍になるかを考えてみると、
2進数のビット列は、左にnビットシフトすると元の値と比べて「2n倍」、右にnビットシフトすると「1／2n倍（2-n倍）」になるという性質があります。
- [xを2ビット左シフト]
x × 22 = x × 4 = 4x … ①
[①にxを加算]
4x + x = 5x … ②
[②を1ビット左シフト]
5x × 21 = 5x × 2 = 10x
結果はxを10倍した値になるので、この操作が正解です。 - [xを2ビット左シフト]
x × 22 = x × 4 = 4x … ①
[①にxを加算]
4x + x = 5x … ②
[②を2ビット左シフト]
5x × 22 = 5x × 4 = 20x
結果はxを20倍した値になるので誤りです。 - [xを3ビット左シフト]
x × 23 = x × 8 = 8x … ①
[xを2ビット左シフト]
x × 22 = x × 4 = 4x … ②
[①と②を加算]
8x + 4x = 12x … ②
結果はxを12倍した値になるので誤りです。 - [xを3ビット左シフト]
x × 23 = x × 8 = 8x … ①
[①にxを加算]
8x + x = 9x … ②
[②を1ビット左シフト]
9x × 21 = 9x × 2 = 18x
結果はxを18倍した値になるので誤りです。