トップ > 情報処理技術者試験 > ２進数の問題を見ると頭が混乱します。

２進数の問題を見ると頭が混乱します。

情報処理技術者試験

前回の勉強内容

ponsuke-tarou.hatenablog.com

2進数の表現の問題

aを正の整数とし，b＝aの2乗 とする。aを2進数で表現するとnビットであるとき，bを2進数で表現すると高々何ビットになるか。

  1. n＋1
  2. 2n
  3. nの2乗
  4. 2のn乗

平成25年春期問1 2進数の表現｜応用情報技術者試験.com

f:id:ponsuke_tarou:20190416193255p:plain
あの日の思い出

「高々」とは、「最大」のことです。

  • 読み方 : たかだか
  • bを2進数で表現すると高々何ビット = bを2進数で表現すると最大何ビット

数学において、高々(たかだか)という表現は、英語の at most に対応した厳密な意味を持つ用語である。
「xは高々2である」という表現は「xは多くとも2である」事、すなわち「x≦2」を意味する。
高々 (数学) - Wikipedia

超地道な解き方：「aを2進数で表現するとnビット」のnに値を入れて考えてみる。

  • aが2bitだと、bの最大は1001で4bitになる
    1. aの最大 = (2進数)11 = (10進数)2 + 1 = (10進数)3
    2. bの最大 = aの2乗 = (10進数)9 = (10進数)8 + 0 + 0 + 1 = (2進数)1001 = 4bit
  • aが3bitだと、bの最大は110001で6bitになる
    1. aの最大 = (2進数)111 = (10進数)4 + 2 + 1 = (10進数)7
    2. bの最大 = aの2乗 = (10進数)49 = (10進数)32 + 16 + 0 + 0 + 0 + 1 = (2進数)110001 = 6bit
  • aが4bitだと、bの最大は11100001で8bitになる
    1. aの最大 = (2進数)1111 = (10進数)8 + 4 + 2 + 1 = (10進数)15
    2. bの最大 = aの2乗 = (10進数)225 = (10進数)128 + 64 + 32 + 0 + 0 + 0 + 0 + 1 = (2進数)11100001 = 8bit
  • aが5bitだと、bの最大は1111000001で10bitになる
    1. aの最大 = (2進数)11111 = (10進数)16 + 8 + 4 + 2 + 1 = (10進数)31
    2. bの最大 = aの2乗 = (10進数)961 = (10進数)512 + 256 + 128 + 64 + 0 + 0 + 0 + 0 + 0 + 1 = (2進数)1111000001 = 10bit
なんかaを1bit増やすとbのbitが2bit(真ん中の10分)増える・・・だから「2n」ですね。

Webツールを使ってちょっと大きめの値で確認してみる

サイトで紹介されている解き方

nけたの正の整数aと、mけたの正の整数bを乗算(a×b)したときのけた数はそれぞれの数字のけた数の和(n+m)を超えることはありません。
この性質は10進数に限ったことではなく、2進数、16進数などでも同じです。また、2進数では必ずけた数の和になります。
問題では2進数nビット(けた)の正の整数aを二乗したときのけた数ですから、
　(n+n)=2n
平成25年 春期 応用情報技術者 午前 問1

　2進数でnビットの最大値は、1111...112ですね（1がn個）。
　これを式変形します。
　　1111...112（※1がn個） = 1000...002（※(n+1)桁。1の後ろに0がn個） - 12
　これを、10進数に直すと、
　　2n - 1
　となります。
　※注：簡単に導出しているように見えますが、実際には簡単な例（n=2のときとか）で確認しています。

　そうしたら、2乗しましょう。
　　(2n - 1)2
　　　　= 22n - 2 * 2n + 1

　これを2進数に直すと、
　　　　= 1000...0002(※(2n+1)桁。1の後ろに0が2n個)
　　　　　- 100..002(※(n+1)桁。1の後ろに0がn個)
　　　　　+ 12
となります。
計算後は、(2n+1)桁よりも小さな値になりますから、2n桁になります。
応用情報H25春 問1の解説 - だるまのエクセルVBA

ビット演算の応用問題

0以上255以下の整数nに対して、https://www.ap-siken.com/kakomon/22_haru/img/01.gifと定義する。next(n)と恒等的に等しい式はどれか。ここで，x AND y 及び x OR y は，それぞれxとyを2進数表現にして，けたごとの論理積及び論理和をとったものとする。

  1. (n＋1) AND 255
  2. (n＋1) AND 256
  3. (n＋1) OR 255
  4. (n＋1) OR 256

平成22年春期問1 ビット演算の応用｜応用情報技術者試験.com

「恒等的に等しい」とは「どのような場合でも等しい」ということらしい

detail.chiebukuro.yahoo.co.jp
oshiete.goo.ne.jp

超地道な解き方：2進数にして論理演算してみます。

  1. nの最大値である255は2進数で書くと1111111となり、nは7bitで書ける範囲ということになります。
  2. n < 255の場合は、next(n) = n + 1 になります。
  3. n = 255の場合は、next(255) = 0になります。
  4. 以下表のようになる論理演算を選ぶわけです。
(10進数)n (10進数)next(n) (2進数)n (2進数)next(n)
255 0 1111111 0000000
254 255 1111110 1111111
2 3 0000010 0000011
1 2 0000001 0000010
0 1 0000000 0000001
  1. 回答群から推理して (n + 1) と (255 か 256) の組み合わせの論理演算になるはずです。
  2. 論理演算下後に (n + 1) になるはずです。
  3. nを7として8bitの2進数表記(256を表すため)で試してみます。

(n＋1) AND 255

10進数 2進数
n+1=8 0000100
255 011111111
AND 0000100

(n＋1) AND 256

10進数 2進数
n+1=8 0000100
256 10000000
AND 0000000

(n＋1) OR 255

10進数 2進数
n+1=8 0000100
255 011111111
OR 011111111

(n＋1) OR 256

10進数 2進数
n+1=8 0000100
256 10000000
OR 1000100
  • 答えは「 ( n + 1) AND 255 」です。

サイトで紹介されている解き方

定義式をみると、０なら１、１なら２と１ずつ足していって２５５だったら０にもどるという。いわゆる２５６進カウンタであることがわかります。これを２進数で考えます。２５５とは１１１１１１１１です。ここで１を加えると０になるので１００００００００が０になる処理を考えると選択肢アが正解だとわかります。
平成18年度春期・ソフ開過去問・解説

ア 『(n +1)AND 255』は、255を2進数で表すと“1111 1111”なので、n =0のとき、next(n )=1になり、n =255のとき、next(n )=0になり、定義と一致する。
イ 『(n +1)AND 256』は、256を2進数で表すと“1 0000 0000”なので、n =0のとき、next(n )=0になり、定義と一致しない。
ウ 『(n +1)OR 255』は、255を2進数で表すと“1111 1111”なので、n =0のとき、next(n )=255になり、定義と一致しない。
エ 『(n +1)OR 256』は、256を2進数で表すと“1 0000 0000”なので、n =0のとき、next(n )=257になり、定義と一致しない。
平成18年 春期 ソフトウェア開発技術者 午前 問3

n が 255 の場合・・・
↓
255+1=256
↓
256と255は2進で
0001 0000 0000
0000 1111 1111
↓
これらの AND は
0000 0000 0000
で、ゼロになります。

255未満で、例えば n が 254 については・・・
↓
254+1=255
↓
255と255は2進で
0000 1111 1111
0000 1111 1111
↓
これらの AND は
0000 1111 1111
で、255 。n＋1 になりました。
恒等式 - 合格☆情報処理技術者試験

f:id:ponsuke_tarou:20190417000727j:plain
思い出の一枚

次回の勉強内容

勉強中・・・