メインコンテンツにスキップ

[再掲載] コンピューターは数値をどう表現しているのか (2)

computer
技術
数値計算
作者

Ryo Nakagami

公開

2020-10-20

更新日

2026-11-18

コンピューターは数値をどう表現しているのか (1) でコンピューターにおける算術演算を解説したので,本記事では関連した練習問題を取り扱います

基本問題

Problem 1

\(a\) を正の整数とし, \(b = a^2\) とする. \(a\) の2進数で表したとき,\(n\) bitであるとすると,このときの \(b\) は何 bitか?

\(a\) の範囲を不等式で表す

\(a\) が2進数で \(n\) bit であることより

\[ 2^{n-1} \le a < 2^{n} \Rightarrow n - 1 \le \log_2 a < n \]

両辺を2乗する

各辺はすべて正なので

\[ 2^{2n-2} \le b = a^2 < 2^{2n}\Rightarrow 2(n - 1) \le \log_2 b < 2n \]

少なくとも \(2n-1\) bit,多くとも \(2n\) bit で表せます.

補足

\(a\) \(a\) の2進数 \(n\) \(b = a^2\) \(b\) の2進数 \(b\) のbit数
4 100 3 16 10000 5 \((= 2n-1)\)
7 111 3 49 110001 6 \((= 2n)\)

より正確には,\(a < \sqrt{2} \cdot 2^{n-1}\) のとき \(2n-1\) bit,\(a \ge \sqrt{2} \cdot 2^{n-1}\) のとき \(2n\) bit になります.

符号なし整数の減算

Problem 2

符号なし整数として \(5\text{ED}4_{(16)} - 07\text{A}4_{(16)}\) を計算し,答えを16進数・2進数・10進数で示せ.

16進のまま引く

各桁を下から順に,16進のまま引きます.この問題では借りは発生しません.

  5 E D 4
− 0 7 A 4
---------
  5 7 3 0
  • \(16^0\) の位:\(4 - 4 = 0\)
  • \(16^1\) の位:\(\text{D}(13) - \text{A}(10) = 3\)
  • \(16^2\) の位:\(\text{E}(14) - 7 = 7\)
  • \(16^3\) の位:\(5 - 0 = 5\)

答え

表記 値
16進数 \(5730_{(16)}\)
2進数 0101 0111 0011 0000
10進数 \(22320\)

Problem 3

符号なし整数として \(4365_{(8)} - 3412_{(8)}\) を計算し,答えを8進数・2進数・10進数で示せ.

8進のまま引く

各桁を下から順に,8進のまま引きます.この問題では借りが1回発生します.

  4 3 6 5
− 3 4 1 2
---------
  0 7 5 3
  • \(8^0\) の位:\(5 - 2 = 3\)
  • \(8^1\) の位:\(6 - 1 = 5\)
  • \(8^2\) の位:\(3 - 4\) は引けないので,上の位から1借りて \(3 + 8 = 11\),\(11 - 4 = 7\)
  • \(8^3\) の位:借りられて \(4 \to 3\) になっているので,\(3 - 3 = 0\)

答え

表記 値
8進数 \(753_{(8)}\)
2進数 111 101 011(8進の各桁を3ビットに直す.\(7 = 111\),\(5 = 101\),\(3 = 011\))
10進数 \(491\)

符号付き整数の減算

符号付き整数の減算 \(A - B\) は,\(A + (-B)\) に置き換えて加算で計算します.\(-B\) の作り方と,最上位からあふれた桁上げの扱いが方式によって異なります.

方式 \(-B\) の作り方 最上位からの桁上げ
2の補数 全ビットを反転して \(+1\) 捨てる
1の補数 全ビットを反転するだけ 最下位に足し戻す(循環桁上げ)

2の補数による減算

Problem 4

16ビットの2の補数表現で \(5\text{ED}4_{(16)} - 07\text{A}4_{(16)}\) を計算せよ.計算の過程を2進数で示し,答えを16進数・10進数でも示せ.

2進数に直す

A = 5ED4 = 0101 1110 1101 0100   (+24276)
B = 07A4 = 0000 0111 1010 0100   (+1956)

\(-B\) を作る

B         = 0000 0111 1010 0100   (07A4)
反転      = 1111 1000 0101 1011   (F85B)
+1        = 1111 1000 0101 1100   (F85C)  ← −1956

\(A + (-B)\) を計算する

    0101 1110 1101 0100   (5ED4)
+   1111 1000 0101 1100   (F85C)
-----------------------
  1 0101 0111 0011 0000   (1 5730)
  ↑ 桁上げは捨てる

16進の桁ごとに見ると,次のとおりです.

  • \(4 + \text{C} = 16 \to 0\),桁上げ1
  • \(\text{D} + 5 + 1 = 19 \to 3\),桁上げ1
  • \(\text{E} + 8 + 1 = 23 \to 7\),桁上げ1
  • \(5 + \text{F} + 1 = 21 \to 5\),桁上げ1(捨てる)

答え

0101 0111 0011 0000 \(= 5730_{(16)} = +22320\) です.

Problem 5

16ビットの2の補数表現で \(4365_{(8)} - 3412_{(8)}\) を計算せよ.計算の過程を2進数で示し,答えを8進数・10進数でも示せ.

2進数に直し,16ビットで表す

8進の1桁は2進の3ビットに対応します.

4365(oct) = 100 011 110 101  → 0000 1000 1111 0101   (08F5, +2293)
3412(oct) = 011 100 001 010  → 0000 0111 0000 1010   (070A, +1802)

\(-B\) を作る

B         = 0000 0111 0000 1010   (070A)
反転      = 1111 1000 1111 0101   (F8F5)
+1        = 1111 1000 1111 0110   (F8F6)  ← −1802

\(A + (-B)\) を計算する

    0000 1000 1111 0101   (08F5)
+   1111 1000 1111 0110   (F8F6)
-----------------------
  1 0000 0001 1110 1011   (1 01EB)
  ↑ 桁上げは捨てる
  • \(5 + 6 = 11 \to \text{B}\),桁上げ0
  • \(\text{F} + \text{F} = 30 \to \text{E}\),桁上げ1
  • \(8 + 8 + 1 = 17 \to 1\),桁上げ1
  • \(0 + \text{F} + 1 = 16 \to 0\),桁上げ1(捨てる)

答え

0000 0001 1110 1011 です.下から3ビットずつ区切ると 111 101 011 なので,\(753_{(8)} = +491\) です.

1の補数による減算

Problem 6

16ビットの1の補数表現で \(5\text{ED}4_{(16)} - 07\text{A}4_{(16)}\) を計算せよ.計算の過程を2進数で示し,答えを16進数・10進数でも示せ.

\(-B\) を作る

全ビットの反転だけで作ります.

B         = 0000 0111 1010 0100   (07A4)
反転      = 1111 1000 0101 1011   (F85B)  ← −1956

\(A + (-B)\) を計算する

    0101 1110 1101 0100   (5ED4)
+   1111 1000 0101 1011   (F85B)
-----------------------
  1 0101 0111 0010 1111   (1 572F)
  • \(4 + \text{B} = 15 \to \text{F}\),桁上げ0
  • \(\text{D} + 5 = 18 \to 2\),桁上げ1
  • \(\text{E} + 8 + 1 = 23 \to 7\),桁上げ1
  • \(5 + \text{F} + 1 = 21 \to 5\),桁上げ1

循環桁上げ

最上位からの桁上げ1を,最下位に足し戻します.

    0101 0111 0010 1111   (572F)
+                     1
-----------------------
    0101 0111 0011 0000   (5730)

答え

2の補数と同じく,0101 0111 0011 0000 \(= 5730_{(16)} = +22320\) です.

Problem 7

16ビットの1の補数表現で \(4365_{(8)} - 3412_{(8)}\) を計算せよ.計算の過程を2進数で示し,答えを8進数・10進数でも示せ.

2進数に直し,16ビットで表す

4365(oct) = 100 011 110 101  → 0000 1000 1111 0101   (08F5, +2293)
3412(oct) = 011 100 001 010  → 0000 0111 0000 1010   (070A, +1802)

\(-B\) を作る

全ビットの反転だけで作ります.

B         = 0000 0111 0000 1010   (070A)
反転      = 1111 1000 1111 0101   (F8F5)  ← −1802

\(A + (-B)\) を計算する

    0000 1000 1111 0101   (08F5)
+   1111 1000 1111 0101   (F8F5)
-----------------------
  1 0000 0001 1110 1010   (1 01EA)

循環桁上げ

最上位からの桁上げ1を,最下位に足し戻します.

    0000 0001 1110 1010   (01EA)
+                     1
-----------------------
    0000 0001 1110 1011   (01EB)

答え

2の補数と同じく,0000 0001 1110 1011 \(= 753_{(8)} = +491\) です.

オーバーフローとアンダーフロー

ここまでの問題では,結果が表せる範囲に収まっていました.この節では,ビット幅を小さくしたときに結果が範囲からはみ出すかどうかを調べます.

Definition 1 整数演算のオーバーフローとアンダーフロー

  • 演算の正しい結果が,\(n\) ビットで表せる範囲の上限を超えることを オーバーフロー という
  • 演算の正しい結果が,\(n\) ビットで表せる範囲の下限を下回ることを,整数の文脈では アンダーフロー(負のオーバーフロー)と呼ぶことがある
  • 表せる範囲は,符号なし整数なら \(0\) 〜 \(2^n - 1\),2の補数表現なら \(-2^{n-1}\) 〜 \(2^{n-1} - 1\),1の補数表現なら \(-(2^{n-1} - 1)\) 〜 \(2^{n-1} - 1\) とする

加算器での検出方法

減算 \(A - B\) を \(A + (\bar{B} + 1)\) として加算器で計算するとき,はみ出しは次のように検出できます.

  • 符号なし:最上位から桁上げが出ないとき,借りが生じている.つまり \(A < B\) で,結果は下限 \(0\) を下回る(アンダーフロー)
  • 符号付き:「正 − 負 = 負」または「負 − 正 = 正」と符号が変わったとき,範囲をはみ出している.回路の上では,符号ビットへの桁上げ入力と,符号ビットからの桁上げ出力が一致しないことで検出する

Problem 8

12ビットの符号なし整数として \(4365_{(8)} - 3412_{(8)}\) を計算せよ.計算の過程を2進数でも示し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ.

2進数に直す

8進数の4桁は,ちょうど12ビットに対応します.

A = 4365(oct) = 100 011 110 101   (2293)
B = 3412(oct) = 011 100 001 010   (1802)

\(\bar{B} + 1\) を作る

B         = 011 100 001 010   (3412)
反転      = 100 011 110 101   (4365)
+1        = 100 011 110 110   (4366)

\(A + (\bar{B} + 1)\) を計算する

    100 011 110 101   (4365)
+   100 011 110 110   (4366)
-------------------
  1 000 111 101 011   (1 0753)
  ↑ 12ビットからあふれた桁上げ

8進の桁ごとに見ると,次のとおりです.

  • \(5 + 6 = 11 \to 3\),桁上げ1
  • \(6 + 6 + 1 = 13 \to 5\),桁上げ1
  • \(3 + 3 + 1 = 7 \to 7\),桁上げ0
  • \(4 + 4 = 8 \to 0\),桁上げ1

答え

結果は 000 111 101 011 \(= 0753_{(8)} = 491\) です.

判定:発生しない

  • \(A = 2293\),\(B = 1802\) はどちらも \(0\) 〜 \(4095\) の範囲に収まる
  • 正しい差 \(2293 - 1802 = 491\) も \(0\) 〜 \(4095\) の範囲に収まる
  • 加算器では最上位から桁上げが出ている.これは借りが生じていない(\(A \geq B\))ことを意味する

したがって,オーバーフローもアンダーフローも発生しません.

Problem 9

\(4365_{(8)}\) と \(3412_{(8)}\) を,12ビットの符号付き整数とみなす.このとき,

  1. 2の補数表現で \(4365_{(8)} - 3412_{(8)}\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ
  2. 1の補数表現で \(4365_{(8)} - 3412_{(8)}\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ

符号付きとして読んだ値

\(4365_{(8)}\) = 100 011 110 101 は最上位ビットが1なので,符号付きでは負の数になります.

8進数 ビット列 符号なし 2の補数 1の補数
\(4365_{(8)}\) 100 011 110 101 \(2293\) \(-1803\) \(-1802\)
\(3412_{(8)}\) 011 100 001 010 \(1802\) \(1802\) \(1802\)
  • 2の補数:最上位ビットの重みが \(-2^{11}\) になるので,\(2293 - 4096 = -1803\)
  • 1の補数:全ビットを反転した 011 100 001 010 \(= 1802\) の負の数なので,\(-1802\).\(4365\) と \(3412\) は桁ごとに足すとすべて7になる(\(7777_{(8)}\))ので,互いの1の補数になっている

(1) 2の補数表現

計算は前問と同じで,\(-B = \bar{B} + 1\) = 100 011 110 110 を足します.

    100 011 110 101   (4365)  ← −1803
+   100 011 110 110   (4366)  ← −1802
-------------------
  1 000 111 101 011   (1 0753)
  ↑ 桁上げは捨てる

結果のビット列は 000 111 101 011 で,2の補数として読むと \(+491\) です.

  • 正しい差 \((-1803) - 1802 = -3605\) は,下限 \(-2048\) を下回る
  • 「負 − 正 = 正」と符号が変わっている
  • 下位11ビットの和 \(245 + 246 = 491 < 2048\) なので,符号ビットへの桁上げ入力は0.一方,符号ビットは \(1 + 1\) で桁上げ出力が1.入力と出力が一致しない

したがって,アンダーフロー(負のオーバーフロー)が発生します.加算器が返す \(+491\) は正しい差ではありません.

(2) 1の補数表現

\(-B\) は全ビットの反転だけで作るので,100 011 110 101(\(4365_{(8)}\) そのもの)です.

    100 011 110 101   (4365)  ← −1802
+   100 011 110 101   (4365)  ← −1802
-------------------
  1 000 111 101 010   (1 0752)
  • \(5 + 5 = 10 \to 2\),桁上げ1
  • \(6 + 6 + 1 = 13 \to 5\),桁上げ1
  • \(3 + 3 + 1 = 7 \to 7\),桁上げ0
  • \(4 + 4 = 8 \to 0\),桁上げ1

最上位からの桁上げ1を,最下位に足し戻します.

    000 111 101 010   (0752)
+                 1
-------------------
    000 111 101 011   (0753)

結果は \(+491\) です.

  • 正しい差 \((-1802) - 1802 = -3604\) は,下限 \(-2047\) を下回る
  • 「負 − 正 = 正」と符号が変わっている

したがって,こちらも アンダーフロー(負のオーバーフロー)が発生します.

符号なしとの比較

加算器が出力するビット列 000 111 101 011 は,符号なしでも2の補数でも同じです.符号なしとして読めば正しい差 \(491\) ですが,符号付きとして読むと \(4365_{(8)}\) が負の数になり,範囲をはみ出します.x86-64 の CPU が,符号なし用の CF と符号付き用の OF という2つのフラグを別々に立てるのはこのためです.

\(4365_{(8)}\) を正の数 \(2293\) として符号付きで計算したいなら,前節のように16ビットで表してから計算します.

Problem 10

12ビットの2の補数 \(4365_{(8)}\),\(3412_{(8)}\) が,16ビットに符号拡張した形式で格納されている.このとき \(4365_{(8)} - 3412_{(8)}\) を計算せよ.計算の過程を2進数で示し,答えを10進数でも示せ.

符号拡張とは

符号拡張は,符号付き整数のビット数を増やすとき,増えた上位ビットを元の符号ビットと同じ値で埋める方法です.2の補数では,こうしても値が変わりません.

  • 符号ビットが0(正の数)なら,上位を0で埋める
  • 符号ビットが1(負の数)なら,上位を1で埋める

2進数に直し,16ビットに符号拡張する

4365(oct) = 100 011 110 101  → 1111 1000 1111 0101   (F8F5, −1803)
3412(oct) = 011 100 001 010  → 0000 0111 0000 1010   (070A, +1802)

\(4365_{(8)}\) は12ビットでの符号ビットが1なので,上位4ビットを1で埋めます.前節の16ビットの問題では上位を0で埋めて \(+2293\) としましたが,ここでは12ビットでの値 \(-1803\) をそのまま16ビットに移しています.

\(-B\) を作る

B         = 0000 0111 0000 1010   (070A)
反転      = 1111 1000 1111 0101   (F8F5)
+1        = 1111 1000 1111 0110   (F8F6)  ← −1802

\(A + (-B)\) を計算する

    1111 1000 1111 0101   (F8F5)
+   1111 1000 1111 0110   (F8F6)
-----------------------
  1 1111 0001 1110 1011   (1 F1EB)
  ↑ 桁上げは捨てる
  • \(5 + 6 = 11 \to \text{B}\),桁上げ0
  • \(\text{F} + \text{F} = 30 \to \text{E}\),桁上げ1
  • \(8 + 8 + 1 = 17 \to 1\),桁上げ1
  • \(\text{F} + \text{F} + 1 = 31 \to \text{F}\),桁上げ1

10進数に直す

結果 1111 0001 1110 1011 は最上位ビットが1なので負の数です.反転して1を足すと絶対値が得られます.

反転      = 0000 1110 0001 0100   (0E14)
+1        = 0000 1110 0001 0101   (0E15 = 3605)

答えは \(-3605\) です.検算すると \((-1803) - 1802 = -3605\) で一致します.

  • 正しい差 \(-3605\) は,16ビットの範囲 \(-32768\) 〜 \(32767\) に収まる
  • 下位15ビットの和 \(\text{78F5} + \text{78F6} = \text{F1EB} \geq \text{8000}\) なので,符号ビットへの桁上げ入力は1.符号ビットは \(1 + 1 + 1\) で桁上げ出力も1.入力と出力が一致する

したがって,オーバーフローは発生しません.

12ビットのままの計算との比較

前問では,同じ \(4365_{(8)} - 3412_{(8)}\) を12ビットのまま計算してアンダーフローが発生し,加算器は \(+491\) を返しました.正しい差 \(-3605\) が12ビットの下限 \(-2048\) を下回るためです.16ビットに符号拡張しておけば,値を変えずに表せる範囲だけが広がるので,正しい差が得られます.

Problem 11

10進数の \(185\) と \(122\) について,

  1. 8ビットの符号なし整数として \(185 - 122\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ
  2. 8ビットの符号付き整数(2の補数表現)として \(185 - 122\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ

2進数に直す

185 = 1011 1001   (128 + 32 + 16 + 8 + 1)
122 = 0111 1010   (64 + 32 + 16 + 8 + 2)

\(\bar{B} + 1\) を作る

B         = 0111 1010   (122)
反転      = 1000 0101   (133)
+1        = 1000 0110   (134 = 256 − 122)

\(A + (\bar{B} + 1)\) を計算する

    1011 1001   (185)
+   1000 0110   (134)
-------------
  1 0011 1111   (319 = 256 + 63)
  ↑ 8ビットからあふれた桁上げ

桁上げを捨てると,結果のビット列は 0011 1111 \(= 63\) です.このビット列は,符号なしでも符号付きでも同じです.

符号なし整数の場合:発生しない

  • \(185\),\(122\) はどちらも \(0\) 〜 \(255\) の範囲に収まる
  • 正しい差 \(185 - 122 = 63\) も \(0\) 〜 \(255\) の範囲に収まる
  • 加算器では最上位から桁上げが出ている.これは借りが生じていない(\(A \geq B\))ことを意味する

したがって,オーバーフローもアンダーフローも発生しません.結果 \(63\) は正しい値です.

符号付き整数(2の補数)の場合:アンダーフローが発生する

8ビットの2の補数で表せるのは \(-128\) 〜 \(127\) です.\(185\) は上限 \(127\) を超えているので,そもそも8ビットの符号付き整数として表せません.

ビット列 1011 1001 を2の補数として読むと,\(-128 + 57 = -71\) です.つまり加算器が実際に計算しているのは \((-71) - 122\) です.

  • 正しい差 \((-71) - 122 = -193\) は,下限 \(-128\) を下回る
  • 「負 − 正 = 正(\(+63\))」と符号が変わっている
  • 下位7ビットの和 \(57 + 6 = 63 < 128\) なので,符号ビットへの桁上げ入力は0.一方,符号ビットは \(1 + 1\) で桁上げ出力が1.入力と出力が一致しない

したがって,アンダーフロー(負のオーバーフロー)が発生します.

Problem 12

10進数の \(185\) と \(122\) について,

  1. 8ビットの符号なし整数として \(185 + 122\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ
  2. 8ビットの符号付き整数(2の補数表現)として \(185 + 122\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ

\(A + B\) を計算する

2進数への変換は前問と同じです.足し算なので,\(B\) をそのまま足します.

    1011 1001   (185)
+   0111 1010   (122)
-------------
  1 0011 0011   (307 = 256 + 51)
  ↑ 8ビットからあふれた桁上げ

桁上げを捨てると,結果のビット列は 0011 0011 \(= 51\) です.このビット列は,符号なしでも符号付きでも同じです.

符号なし整数の場合:オーバーフローが発生する

  • \(185\),\(122\) はどちらも \(0\) 〜 \(255\) の範囲に収まる
  • 正しい和 \(185 + 122 = 307\) は,上限 \(255\) を上回る
  • 加算器では最上位から桁上げが出ている.足し算での桁上げは,結果が8ビットに収まらないことを意味する

したがって,オーバーフローが発生します.結果 \(51\) は,正しい和 \(307\) から \(2^8 = 256\) を引いた値で,正しい値ではありません.

\(A + B\) を計算する

加算器が出力するビット列は (1) と同じ 0011 0011 で,最上位からの桁上げも1です.

    1011 1001   (185 → 符号付きでは −71)
+   0111 1010   (122)
-------------
  1 0011 0011   (51)
  ↑ 桁上げは捨てる

符号付き整数(2の補数)の場合:発生しない

前問と同じく,\(185\) は上限 \(127\) を超えているので,8ビットの符号付き整数としては表せません.ビット列 1011 1001 を2の補数として読むと \(-71\) なので,加算器が実際に計算しているのは \((-71) + 122\) です.

  • 正しい和 \((-71) + 122 = 51\) は,\(-128\) 〜 \(127\) の範囲に収まる
  • 「負 + 正」は符号が異なる数どうしの足し算なので,そもそもオーバーフローは起こりえない
  • 下位7ビットの和 \(57 + 122 = 179 \geq 128\) なので,符号ビットへの桁上げ入力は1.符号ビットは \(1 + 0 + 1\) で桁上げ出力も1.入力と出力が一致する

したがって,オーバーフローもアンダーフローも発生しません.結果 \(51\) は \((-71) + 122\) の正しい値です.

論理演算

Problem 13

\(m\) を正の整数とする.次の2つが同値であることを示せ.

  1. すべての非負整数 \(x\) に対して \(x \mathbin{\mathrm{AND}} (m-1) = x \bmod m\)
  2. \(m\) は 2 のべき乗である(ある整数 \(k \ge 0\) で \(m = 2^k\))

非負整数 \(x\) の2進展開を \(x = \sum_{i \ge 0} b_i 2^i\)(\(b_i \in \{0,1\}\))と書きます.

(2) ⇒ (1)

\(m = 2^k\) とする.\(m - 1 = 2^k - 1 = \sum_{i=0}^{k-1} 2^i\) なので,\(m-1\) は下位 \(k\) ビットがすべて 1,それより上がすべて 0.AND は桁ごとの論理積なので,

\[ r := x \mathbin{\mathrm{AND}} (m-1) = \sum_{i=0}^{k-1} b_i 2^i \]

となります.この \(r\) について次の2点が成り立つ.

  • 範囲:\(0 \le r \le \sum_{i=0}^{k-1} 2^i = 2^k - 1\),すなわち \(0 \le r < m\)
  • 合同:\(x - r = \sum_{i \ge k} b_i 2^i = 2^k \sum_{i \ge k} b_i 2^{i-k}\) なので,\(x - r\) は \(m\) の倍数

除法の原理より,\(x = qm + r\) かつ \(0 \le r < m\) を満たす \(r\) は一意で, \(x \bmod m\) .よって \(x \mathbin{\mathrm{AND}} (m-1) = x \bmod m\) .

(1) ⇒ (2)

条件 (1) で \(x = m\) とおくと,\(m \bmod m = 0\) なので

\[ m \mathbin{\mathrm{AND}} (m-1) = 0 \quad\cdots (\ast) \]

が必要.これが \(m\) を 2 のべき乗に限定することを示します.

\(m \ge 1\) なので,\(m\) の2進展開で 1 が立っている最下位の位を \(2^j\) の位とすると,ある整数 \(a \ge 0\) を用いて

\[ m = a \cdot 2^{j+1} + 2^j \]

と書ける.このとき

\[ m - 1 = a \cdot 2^{j+1} + (2^j - 1) \]

両者を桁ごとに比べる.

  • \(2^{j+1}\) の位以上:どちらも \(a\) のビット列で一致するので,AND を取ると \(a\) がそのまま残る
  • \(2^j\) の位:\(m\) は 1,\(m-1\) は 0 なので,AND は 0
  • \(2^{j-1}\) の位以下:\(m\) はすべて 0 なので,AND は 0(\(j = 0\) のときはこの範囲の位がない)

したがって \(m \mathbin{\mathrm{AND}} (m-1) = a \cdot 2^{j+1}\).\((\ast)\) よりこれが 0 なので \(a = 0\),すなわち \(m = 2^j\).\(\blacksquare\)

系:2 のべき乗の判定法

\(m \ge 1\) が 2 のべき乗であることと \(m \mathbin{\mathrm{AND}} (m-1) = 0\) は同値.

  • 2 のべき乗 ⇒ \(m \mathbin{\mathrm{AND}} (m-1) = 0\):(2) ⇒ (1) で \(x = m\) とおくと \(m \mathbin{\mathrm{AND}} (m-1) = m \bmod m = 0\)
  • \(m \mathbin{\mathrm{AND}} (m-1) = 0\) ⇒ 2 のべき乗:(1) ⇒ (2) の後半の議論そのもの

よって,2 のべき乗の判定式は

(m & (m - 1)) == 0