科目Bのビット演算問題の解き方｜論理積とシフトを2進数で追う

∧ とか >> とか、記号を見た瞬間に手が止まってしまう。

科目Bの問題で、見慣れない記号が並んだコードに出会って、そこで読むのをあきらめたことはありませんか？

配列やループの問題なら追えるのに、ビット演算になると急に別の科目のように感じる。そんな人は多いのではないでしょうか。

大丈夫です。ビット演算の問題で必要なのは、値を10進数ではなく2進数で書くことと、1桁ずつそろえて計算する手順だけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、ユーザーの権限や設定のオンとオフを1つの整数のビットにまとめて持たせる設計に何度も出会っています。

どのビットが立っているかを読み違えて、見せてはいけない画面が見えてしまう不具合を調べたこともあります。そのときに役立ったのは、難しい知識ではなく、値を2進数で紙に書き出す地味な作業でした。

この記事では、ビット演算の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中で、こうした問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

ビット演算の問題は何を聞いているのか¶

最初に、ビット演算とは何かを短く押さえておきましょう。何のための計算なのかが分かると、コードの意図がぐっと読みやすくなります。

ビット演算とは、整数を2進数で表したときの各桁、つまり各ビットごとに行う計算のことです。足し算のような繰り上がりはなく、桁どうしを縦にそろえて、それぞれ独立に答えを出します。

試験で問われるのは、ある値に演算を何回か施したあと、最後にどんな値が残るかです。あるいは、目的の処理になるように空欄へどの演算を入れるかが問われます。

よく出る4つの演算¶

科目Bの問題では、演算子の意味が問題文の中で説明されることがほとんどです。それでも、意味を先に知っていれば、説明を読む時間を大きく減らせます。

この記事で使う4つの演算を、8ビットの例で表にまとめました。

表の例は、桁数を見やすくするために一部を4桁で書いています。実際の問題では、何ビットの値を扱うのかが問題文に書かれるので、その桁数にそろえて考えます。

and や or との違い¶

ここでよく混同されるのが、if 文の条件で使う and や or です。and と or は、条件全体が真か偽かを決めるための演算でした。

一方の ∧ と ∨ は、数値の各桁を計算して、新しい数値を作ります。答えが真か偽ではなく整数になる、という点がいちばんの違いです。

条件式の and や or の読み方に不安がある場合は、こちらの記事で先に整理しておくと、両者の違いがはっきりします。

【関連記事】擬似言語の論理演算（and・or・not）の読み方｜複合条件で迷わないコツを解説

まず目を付ける場所¶

ビット演算とは何かがつかめたら、次はコードのどこから読むかを決めます。ビット演算の問題では、目を付ける場所が3つあります。

ひとつ目はビットの幅、ふたつ目は ∧ や ∨ の相手になっている値、みっつ目はシフトの向きと回数です。この順番で見ていくと、コードの役割がはっきりします。

ビットの幅を最初に確かめる¶

最初に見るのは、扱う値が何ビットなのかです。8ビットなら、どんな値も8桁の2進数で書けます。

幅が決まると、シフトではみ出したビットがどうなるかも決まります。8ビットの 11000000 を左に1つずらすと、左端の1は押し出されて消え、10000000 になります。

10進数のまま2倍して 384 と書いてしまうと、ここで答えがずれます。幅を超えた分は消える、と覚えておきましょう。

∧ の相手は取り出したい桁を表す¶

次に見るのは、∧ や ∨ の右側に置かれた値です。この値はマスクと呼ばれ、どの桁に注目しているのかを表しています。

たとえば x ∧ 1 は、1 が 00000001 なので、x の右端の1桁だけを残して、ほかをすべて0にします。結果が1なら右端は1、0なら右端は0だと分かります。

同じように、x ∨ 1 は右端の桁を必ず1にします。∧ は桁を取り出すとき、∨ は桁を立てるときに使う、と考えると読みやすくなります。

例題：1になっているビットを数える¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のコードは、8ビットの符号なし整数 x を受け取り、1になっているビットがいくつあるかを数える関数です。この例題では、8ビットの符号なし整数を表す型を 8ビット型 と書くことにします。

○整数型: countOnes(8ビット型: x)
  整数型: count ← 0
  8ビット型: r ← x
  while (r が 0 と等しくない)
    if ((r ∧ 1) が 1 と等しい)
      count ← count + 1
    endif
    r ← r >> 1
  endwhile
  return count

まず、r ∧ 1 で右端の1桁だけを取り出し、それが1なら count を1増やします。そのあと r を右に1つずらして、次の桁を右端に持ってきます。

これを r が0になるまで繰り返せば、1のビットを1つ残らず数えられます。では、x に 178 を渡すと、戻り値はいくつになるでしょうか？

10進数を2進数に直す¶

178 を2進数に直すと 10110010 です。8ビットなので、ちょうど8桁で書けます。

直し方に迷ったら、128、64、32、16、8、4、2、1 の重みを左から並べてみてください。178 は 128 ＋ 32 ＋ 16 ＋ 2 なので、その位置に1を置けば完成です。

試験本番では、問題文に2進数のまま値が示されることもあります。その場合は、無理に10進数へ直さず、2進数のまま追うほうが速くて確実です。

トレース表で2進数を追う¶

頭の中だけでシフトを繰り返すと、何回ずらしたのか分からなくなりがちです。そこで、ループ1回ごとの r と、r ∧ 1 の結果、count をトレース表に書きます。

ポイントは、r を必ず8桁の2進数で書くことです。桁をそろえておけば、右端の1桁が何かを一目で確かめられます。

8回目のあと r は 00000000 になり、r が0と等しくないという条件が偽になってループを抜けます。戻り値は 4 です。

10110010 の中にある1を数えても、確かに4個あります。表の結果と見比べて一致すれば、追い方は合っています。

右シフトは2で割った商と同じ¶

表の r を10進数に直してみると、面白いことが分かります。178、89、44、22、11、5、2、1 と、毎回2で割った商になっているのです。

符号なしの整数では、右に1つずらすことは、2で割って余りを捨てることと同じです。そして r ∧ 1 は、r を2で割った余りと同じ値になります。

つまりこの関数は、r mod 2 と r ÷ 2 の商を使っても書き換えられます。余りと割り算の考え方そのものを確かめたい場合は、こちらの記事が参考になります。

【関連記事】擬似言語の余り（剰余）と割り算がわからない人へ｜偶数判定と桁の取り出しを解説

左シフトと論理和で値を組み立てる¶

右シフトと論理積で桁を取り出す処理と対になるのが、左シフトと論理和で桁を積み上げる処理です。取り出した桁を、別の変数の右端へ順に足していく形がよく使われます。

たとえば、y ← (y << 1) ∨ (r ∧ 1) という1行を考えてみましょう。y を左に1つずらして右端を空け、そこに r の右端の桁を入れています。

この1行を8回繰り返すと、r から取り出した順に桁が並ぶので、ビットの並びが左右逆になった値が y にできあがります。y が 00000101 で r の右端が 1 なら、y は 00001010 を経て 00001011 になる、という具合です。

間違いやすい選択肢の見分け方¶

ビット演算の問題では、記号や数値を少しだけ変えた選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

よくある誤りを表にまとめました。

この中でも、特によく狙われるのが ∧ と ∨ の取り違えと、シフトの向きです。順番に見ていきましょう。

∧ は取り出す、∨ は立てる¶

∧ と ∨ で迷ったら、マスクの1を相手に計算した結果を考えてみてください。何かと1の論理積は元の桁のまま残り、何かと1の論理和は必ず1になります。

つまり、桁を調べたいなら ∧、桁を1にしたいなら ∨ です。選択肢の式が、コードの目的と合っているかを、この一点で確かめられます。

もう一つ覚えておくと便利なのが、0 との組み合わせです。何かと0の論理積は必ず0になるので、∧ でマスクの0に当たる桁は消える、と考えられます。

シフトの向きは記号の向きで覚える¶

<< と >> は、記号が指している向きにビットが動く、と覚えるのがいちばん簡単です。<< なら左へ、>> なら右へ動きます。

迷ったときは、00000110 のような小さな値を1回だけずらしてみてください。左なら 00001100 で2倍、右なら 00000011 で半分になります。

選択肢で迷ったら、この記事の例題のように、3桁か4桁に1が混ざった小さな値を用意して、1回分だけ計算してみることをおすすめします。結果が目的と合わない選択肢は、その1回で見分けられます。

桁を読み違えないための確認¶

ビット演算でいちばん多いのは、考え方の誤りではなく、桁のずれです。8桁のつもりで7桁しか書いていない、というだけで答えは変わってしまいます。

トレース表を書くたびに、桁数が8つあるかを指で数えて確かめましょう。小さな確認ですが、それだけで防げるミスはたくさんあります。

数え間違いや読み飛ばしのような、うっかりミス全般の防ぎ方は、こちらの記事でまとめています。

【関連記事】擬似言語でケアレスミスが多い人へ｜よくある間違いと確認方法

トレース表を書く作業そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。値が何度も変わる処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの回で予想とずれたのかがすぐに分かります。

試すときは、先ほどの書き換えを使うのがおすすめです。r ∧ 1 を r mod 2 に、r >> 1 を r ÷ 2 の商に置き換えたコードを動かし、r の値が 178、89、44 と変わっていく様子を見てみてください。

10進数の動きと、紙に書いた2進数の表を並べて見ると、右シフトが2で割ることと同じだという感覚が自然に身につきます。渡す値を 255 や 128 に変えて、ループの回数がどう変わるかを試してみるのも良い練習です。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、値が1行ごとに変わっていく様子を確かめてみてください。

まとめ¶

科目Bのビット演算の問題は、2進数の深い理論を問うものではありません。値を桁をそろえた2進数で書き、1回ごとにトレース表を更新していけば必ず解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、4桁か8桁の小さな値で十分です。1つの値を何回かずらしては表に書く練習を繰り返すうちに、>> 1 を見ただけで、右端の桁が1つずつ消えていく様子が思い浮かぶようになります。

記号が見慣れなくても、中でやっていることは桁を縦にそろえて1つずつ計算する、の繰り返しです。次にビット演算の問題に出会ったら、まずは値を2進数で書き出すところから始めてみてください。