前回までのお話

『2進数と10進数の対応を眺めることで、複数の選択状態をたった一つの10進数数値で表現することができる』
『複数選択状態を表現している10進数値から選択状態を判定する時はビットマスクで & する』
という内容をコラムの1と2で紹介しました。

2進数と10進数を並べてみると、
000 = 0
001 = 1 (1桁目のビットマスク)
010 = 2 (2桁目のビットマスク)
011 = 3
100 = 4 (3桁目のビットマスク)
101 = 5
110 = 6
111 = 7

今回は奇数偶数判定をネタとして紹介します。
プログラムの入門書に書いてる数学的な記述だけではなく、ビットマスクで別の書き方ができる、というネタですが、2進数に置き換えて考えるとこういう書き方もあるという話を紹介しているだけなので、すでに知っている人は特に読まれる必要はないかと思います。

今回は奇数偶数判定を考えてみます

数学的に式で書くと、奇数は「2n + 1」で偶数は「2n」、授業ではその証明方法とかを勉強したのではないかと思ったりします。式の意味は、奇数は2で割り切れない、偶数は2で割り切れる。というものですね。

なのでプログラムで奇数・偶数判定する時は、2で割って、余りがあるかどうかを数学で習ったままに書いたりするかと思います。

if(x%2!==0){
//余りが0でないので、奇数の場合の処理
}
else{
//余りが0なので、偶数の場合の処理
}
又は
if(x%2===0){
//余りが0なので、偶数の場合の処理
}
else{
//余りが0でないので、奇数の場合の処理
}

プログラムのテクニックとして、0は偽、0以外の数値は真

プログラマは基本的にめんどくさがりなのでプログラムを短く書こうとしたり、効率的な処理記述を目指す人が多いかと思います。
なので、if(x%2!==0)という部分は、「余りを求める処理」と「その結果が0かどうかを判定する処理」の二つをやっている点について、以下のように書いて処理を単純にしたりする場合があるかと思います。

if(x%2){
//余りが0でない
// → ifの条件式の結果が真なので、奇数の場合の処理
}
else{
//余りが0
// → ifの条件式の結果が偽なので、偶数の場合の処理
}

これはif判定部分で、0は偽、0以外の数値は真となっているルールを利用した書き方になります。

2進数に変換して並べて眺めてみる

2進数と10進数を並べてみると、
000 = 0 偶数(今回の紹介では偶数としておきます)
001 = 1 奇数
010 = 2 偶数
011 = 3 奇数
100 = 4 偶数
101 = 5 奇数
110 = 6 偶数
111 = 7 奇数

0は0なので、偶数とするのかどうかは数学的な話ですが、プログラムでやろうとする処理によって、どうするかが変化する話かと思いますので、とりあえず今回の紹介では偶数側にしておきます。

2進数にした時の縦の並びを眺めるだけで、勘のいい人は前回記事と合わせて答えが見えてくるのではないかと思ったりします。
ヒントはビットマスクです。

奇数ごと、偶数ごとに並べてみる

偶数だけ / 奇数だけを縦に眺めてみてください。
000 = 0 偶数 / 001 = 1 奇数
010 = 2 偶数 / 011 = 3 奇数
100 = 4 偶数 / 101 = 5 奇数
110 = 6 偶数 / 111 = 7 奇数
2進数の1桁目に注目すると、偶数は0、奇数は1になっています。

数学の式でも偶数が 2n で、奇数が 2n +1 なので、奇数と偶数が交互に並ぶのは一般的な知識かと思います。

覚えておくと便利、というネタとして以前の記事で書いてたように、2進数の各桁のみが1である値、すなわちビットマスクの値は、2の階乗になっていて、10000 = 16 = 2の4乗 = 2*2*2*2 , 01000 = 8 = 2の3乗 = 2*2*2 , 00100 = 4 = 2の2乗 = 2*2 , 00010 = 2 = 2の1乗 = 2 , 00001 = 1 = 2の0乗 = 1、という数値になるのですが、2の0乗以外は、2の掛け算でできている値なので、偶数になります。2進数のビットマスクは 2の0乗、すなわち 1 だけが奇数なのです。

2進数で数値を表す時はビットマスクの足し算ですべて表現していますので、1桁目が 0 の場合のビットマスクの足し算の結果は 偶数 + 偶数 なので、偶数にしかなりません。
ということで、2進数の1桁目が0の場合は偶数、2進数の1桁目が1の場合は奇数だと判定できる、ということになります。

1桁目のビットマスクで&する

2進数の1桁目が0の場合は偶数、1の場合は奇数だと判定できる、とわかりましたので、前回のビットマスクと&する話が使える、ということになります。

2進数の1桁目のビットマスク 001 は 10進数では 1 ですので…

if(x&1){
//1桁目が1
// → ifの条件式の結果が真なので、奇数の場合の処理
}
else{
//1桁目が0
// → ifの条件式の結果が偽なので、偶数の場合の処理
}

前回参照したwikipediaさんの記事でも書いてあったように、掛け算・割り算などよりも、ビット演算の方が処理が軽い、ということなので、プログラム中に大量にこういう判定がある場合はビット演算した方が全体の処理としては軽くなる、かと思います。

豆知識：10進数を2進数に変換（と奇数と偶数の関係）について

2進数ですべての正の整数を表現して計算しているのですが、2進数の1桁目以外の桁は2の階乗の値なので、2進数の各桁だけが1の数値（＝ビットマスク）は1桁目以外はすべて偶数、ということになります。（2n） で、1桁目が1なら 2n + 1 で奇数、ということになります。

10進数を2進数に変換する時の計算方法は、順番に2で割ってゆき、余りがあれば1、なければ0を後ろから並べ、商が1になったら頭に付加する、というのを習ったりします。
8の場合 8/2=4…0 4/2=2…0 2/2=1…0 商が1 → [1000]
7の場合 7/2=3…1 3/2=1…1 商が1 → [111]

この計算も、奇数の場合は最後が1、偶数なら0で、さらに、2進数の各桁が1の数値の足し算であると知っていると、 例えば123の場合、ビットマスクで一番近いのが64(次の128は123より大きい)となり、 123-64=59、次に近いのが32で59-32=27、27-16=11、11-8=3、3-2=1、なので、
123 = 64 + 32 + 16 + 8 + 2 + 1
= 2の6乗 + 2の5乗 + 2の4乗 + 2の3乗 + 2の1乗 + 2の0乗
= 1111011 と計算することもできます。
※0乗を1桁目、6乗は7桁目で、2の2乗の桁（3桁目）のみがない → 3桁目のみ0で後は1

ということで、数値xについて、x&1 が真なら奇数、偽なら偶数と判定することができるようになりました

数学で 2n が偶数、2n +1 が奇数と習い、2進数に変換して考えてみると、1桁目が0なら偶数、1なら奇数という数字の特徴から、x&1が真なら奇数、偽なら偶数というプログラムでの使い方を紹介しました。

別に、x&1 は奇数偶数判定専用の計算ではなく、単なるビット演算ですので、単純に2進数の各桁を1(10進数)で & した結果、つまりは 2進数の 1桁目が 0 なのか、1 なのかをコンピュータは計算処理しているだけです。

ですが、前回の2進数を旗が立つとか、複数を選択している、のように別の意味を人間が考えて、その計算結果を後のプログラムで意味づけするように、今回の2進数1桁目のビットマスクで&演算した結果に、奇数偶数判定に使うという意味を与えるようにプログラムの処理を書くことで、単なる計算がアイデアになる、
これが今回紹介したお話のテーマです。

ネット検索すると今回紹介したような説明がないまま、とりあえず、奇数偶数判定はそう書く、みんながそう書いてるからそう書け的な、記事があったりしましたので、2進数とビット演算の活用ネタをテーマとしている今回の記事に取り上げてみました。

とりあえず、お疲れさまでした。