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

前回の勉強内容

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 」です。

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

定義式をみると、0なら1、1なら2と1ずつ足していって255だったら0にもどるという。いわゆる256進カウンタであることがわかります。これを2進数で考えます。255とは11111111です。ここで1を加えると0になるので100000000が0になる処理を考えると選択肢アが正解だとわかります。
平成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
思い出の一枚

次回の勉強内容

勉強中・・・