うごく基本情報

サンプル問題セット(2022年12月公開) 科目B 問16

基数変換 ・ 割り算と余り ・ 文字コード

次のプログラム中の[ ]に入れる正しい答えを,解答群の中から選べ。二つの[ ]には,同じ答えが入る。ここで,配列の要素番号は 1 から始まる。
Unicode の符号位置を,UTF-8 の符号に変換するプログラムである。本問で数値の後ろに“(16)”と記載した場合は,その数値が 16 進数であることを表す。
Unicode の各文字には,符号位置と呼ばれる整数値が与えられている。UTF-8 は,Unicode の文字を符号化する方式の一つであり,符号位置が 800(16) 以上 FFFF(16)以下の文字は,次のように 3 バイトの値に符号化する。
3 バイトの長さのビットパターンを[ ]1110xxxx 10xxxxxx 10xxxxxx とする。ビットパターンの下線の付いた“x”の箇所に,符号位置を 2 進数で表した値を右詰めで格納し,余った“x”の箇所に,0 を格納する。この 3 バイトの値が UTF-8 の符号である。
例えば,ひらがなの“あ”の符号位置である 3042(16) を 2 進数で表すと11000001000010 である。これを,上に示したビットパターンの“x”の箇所に右詰めで格納すると,1110xx11 10000001 10000010 となる。余った二つの“x”の箇所に 0を格納すると,“あ”の UTF-8 の符号 11100011 10000001 10000010 が得られる。
関数 encode は,引数で渡された Unicode の符号位置を UTF-8 の符号に変換し,先頭から順に 1 バイトずつ要素に格納した整数型の配列を返す。encode には,引数として,800(16) 以上 FFFF(16) 以下の整数値だけが渡されるものとする。

○整数型の配列: encode(整数型: codePoint)
  /* utf8Bytesの初期値は,ビットパターンの“x”を全て0に置き換え,
     8桁ごとに区切って,それぞれを2進数とみなしたときの値 */
  整数型の配列: utf8Bytes ← {224, 128, 128}
  整数型: cp ← codePoint
  整数型: i
  for (i を utf8Bytesの要素数 から 1 まで 1 ずつ減らす)
    utf8Bytes[i] ← utf8Bytes[i] + (cp ÷ [ a ] の余り)
    cp ← cp ÷ [ a ] の商
  endfor
  return utf8Bytes
a
ア((4 - i) × 2)
イ(2 の (4 - i)乗)
ウ(2 の i 乗)
エ(i × 2)
オ2
カ6
キ16
ク64
ケ256

出典:基本情報技術者試験 科目B試験 サンプル問題セット(2022年12月公開) 問16

正解と解説を見る

正解:ク

ポイント:UTF-8 の2バイト目以降は下位6ビットずつ持つ → 64(=2の6乗)で割った余りを入れ、商を次へ回す。

3バイトのUTF-8は、ビットパターンが 1110xxxx 10xxxxxx 10xxxxxx です。x の部分に、コードポイントのビットを下位から順に詰めます。2バイト目と3バイト目の x は6ビットずつ、1バイト目の x は4ビットです。
プログラムは、i を3(最後のバイト)から1へ減らしながら、utf8Bytes[i] に「cp を何かで割った余り」を足し、cp をその商にします。下位6ビットを取り出すには 2⁶=64 で割った余りを取ればよく、商を取ると6ビット右にずれます。よって空欄は 64(ク)。
1バイト目のときも 64 で割りますが、残っているのは上位4ビット分だけ(コードポイントが 16 ビットに収まる範囲)なので、余りはそのまま4ビットの値になります。
例:「あ」U+3042 は 0011 000001 000010 と分けられ、224+3、128+1、128+2 = {227, 129, 130} になります。

解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。

正解のプログラムを動かしてみる

encode(2048) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 15 手)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目○整数型の配列: encode(整数型: codePoint)codePoint = 2048
24行目整数型の配列: utf8Bytes ← {224, 128, 128}utf8Bytes = {224, 128, 128}
35行目整数型: cp ← codePointcp = 2048
46行目整数型: i
57行目for (i を utf8Bytesの要素数 から 1 まで 1 ずつ減らす)真
i = 3
68行目utf8Bytes[i] ← utf8Bytes[i] + (cp ÷ 64 の余り)
79行目cp ← cp ÷ 64 の商cp = 32
87行目for (i を utf8Bytesの要素数 から 1 まで 1 ずつ減らす)真
i = 2
98行目utf8Bytes[i] ← utf8Bytes[i] + (cp ÷ 64 の余り)utf8Bytes = {224, 160, 128}
109行目cp ← cp ÷ 64 の商cp = 0
117行目for (i を utf8Bytesの要素数 から 1 まで 1 ずつ減らす)真
i = 1
128行目utf8Bytes[i] ← utf8Bytes[i] + (cp ÷ 64 の余り)
139行目cp ← cp ÷ 64 の商
147行目for (i を utf8Bytesの要素数 から 1 まで 1 ずつ減らす)偽
i = 0
1511行目return utf8Bytes

戻り値:{224, 160, 128}

サイトで、1行ずつ予想しながら動かす →