離散数学(全64問中62問目)
No.62解説へ
数値を2進数で表すレジスタがある。このレジスタに格納されている正の整数 x を10倍する操作はどれか。ここで，シフトによるあふれ(オーバーフロー)は，起こらないものとする。
出典：平成17年春期 問 1
- xを2ビット左にシフトした値にxを加算し，更に1ビット左にシフトする。
- xを2ビット左にシフトした値にxを加算し，更に2ビット左にシフトする。
- xを3ビット左にシフトした値と，xを2ビット左にシフトした値を加算する。
- xを3ビット左にシフトした値にxを加算し，更に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倍した値になるので誤りです。
広告