FE SUBJECT B
基本情報技術者 科目Bの問題解説：次の手続 bitCount(13) を実行したときの戻り値は…
問題
次の手続 bitCount(13) を実行したときの戻り値はどれか。
○整数型: bitCount(整数型: n)
整数型: c ← 0
while (n ＞ 0)
c ← c ＋ (n mod 2)
n ← n ÷ 2 の商
endwhile
return c- ア 2
- イ 3（正解）
- ウ 4
- エ 13
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：3
n mod 2 は最下位ビットを取り出し、n ÷ 2 の商 はビット列を右へ1つずらす操作に相当します。したがって、この手続は2進表現に含まれる1の個数を数えています。
13は2進数で1101であり、1は3個あります。実際のループでも、13 mod2=1、6 mod2=0、3 mod2=1、1 mod2=1 を足すので、cは3になります。nそのものの値やループ回数ではなく、各回で得た余りだけを合計する点が誤答防止のポイントです。
| n | n mod 2 | c |
|---|---|---|
| 13 | 1 | 1 |
| 6 | 0 | 1 |
| 3 | 1 | 2 |
| 1 | 1 | 3 |
| 0 | - | 終了 |
このアルゴリズムの正体と計算量：これは2進表現中の1の個数を数える「ポップカウント（popcount）」です。1回の繰り返しで n ÷ 2 の商 によりnの桁が1つ減るため、ループ回数はnのビット幅に比例し、計算量はO(log n)です。13なら1101の4桁なので4回回ります。なお「立っているビットだけ」を消すKernighan法を使えば、1の個数（ここでは3回）に比例した処理に短縮できます。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。