2進数で2の倍数判定

Algorithm

2の倍数判定アルゴリズムです。

2の倍数ということは、2で除算した余りが0であるということです。
すなわち、偶数であるということです。

偶数と奇数の定義

偶数とは?

2で除算した余りが0になる数。対義語は奇数。

2進数の場合は、下1桁の数字が「0」であれば偶数である。
10進数の場合は、下1桁の数字が「0、2、4、6、8」であれば偶数である。

奇数とは?

2で除算した余りが1になる数。対義語は奇数。

2進数の場合は、下1桁の数字が「1」であれば偶数である。
10進数の場合は、下1桁の数字が「1、3、5、7、9」であれば奇数である。

余談ですが「0は偶数に含めるか?」という議論があります。

  • 「0÷2=0あまり0」だから偶数である。
  • 0の由来は「存在しない数」だから、偶数でも奇数でもない。

まあ、僕は0は偶数に含めるタイプです。
偶数の定義に従うと「0÷2=0あまり0」になるからです。

2で除算して余り0であるか判定する

「2で除算して余り0であるかを判定する」偶数の定義に従った最も簡単な方法です。

// valueは整数
int value;

// 2で除算した余りを判定
if ((value % 2) == 0)
{
  // 偶数です。
  return true;
}
else
{
  // 奇数です。
  return false;
}

シフト演算で下1桁だけを残して判定する

コンピューターは2進数で処理をしています。2進数の特徴上、次の法則が成り立ちます。

2進数の場合は、下1桁の数字が「0」であれば偶数である。

2進数は2の倍数で繰り上がり、それに伴い下1桁が0になる。

すなわち、下1桁だけで2の倍数を判定できるのです。

今回は左シフト演算で下1桁だけを残します。

// valueは整数
int value;

// intは32bitのため、左に31シフトする
if ((value << 31) == 0x80000000)
{
  // 偶数です。
  return true;
}
else
{
  // 奇数です。
  return false;
}

IF構文の数値(80000000)の表記は次の通りです。

進数表記数値表記
2進数10000000_00000000_00000000_00000000
10進数2,147,483,648
16進数80,000,000

2進数表記で最上位にだけ1が立つ数字を使って2の倍数判定します。

論理積で下1桁だけを残して判定する

こちらも下1桁だけを残す方法です。

// valueは整数
int value;

// 1との論理積を取る
if ((value & 1) == 0)
{
  // 偶数です。
  return true;
}
else
{
  // 奇数です。
  return false;
}

IF構文の数値(1)の表記は次の通りです。

進数表記数値表記
2進数1
10進数1
16進数1

1は2進数表記でも最下位だけに1が立つ数字です。

1との論理積を求めることで、下1桁以外のビットを0に変えます。
すなわち、すべての整数を「0」か「1」かの2種類に直すことができます。

後は「偶数である0と等しいか?」で判定することで2の倍数判定ができます。

 

コメント

タイトルとURLをコピーしました