どうも, ビット演算が好きなたぬきです。
ビット演算でググったら結構上の方に来る某記事で「数学では使用しない」と書かれてて「んお
」ってなったので書きました。 $x \in \{0, 1\}$ のベクトル上の演算として考察している記述は結構見つかるのですが, 自然数の集合上の演算としての考察があまり見当たらないんですよな。 多分こっちのほうがスッキリすると思うんですけど(名推理)。
なお, シフト演算に関しては扱いません。 熱烈なシフト演算ファンのみなさん許し亭許して。 ぶっちゃけ $2^n$ だしやらなくてもええやろ……(小声)。
\def\xor{\mathbin{\small \triangle}}
\def\suc{\mathop{\text{suc}}}
\def\coloneqq{\mathbin{:=}}
\def\xmapsto#1{\overset{#1}{\mapsto}}
基本的なことおさらい
あまり想定読者の前提知識を多く見積もるといろいろな人に読んでもらえないし, 逆につよい人が現れてにわか数学クラスタの僕なんかはマサカリでズタズタにされてもおかしくないので, ちょっとした数学講座をやりましょう。 多分語弊だらけなんで数学のつよい人は僕の数学力について察してください。
集合
ものの集まりのことを数学においては集合とよび, その構成成分を元と呼びます。 自然数の集合における元とは, $3$ とか $42$ とか, なんかそんな感じですね。 集合 $S$ に元 $a$ が含まれていることを, $a \in S$ のように表記します。
集合 $S$ の元がすべて集合 $T$ に含まれているとき, $S$ は $T$ の部分集合であるといい, $S \subseteq T$ のように表記します。 集合 $S$ が集合 $T$ の部分集合であるけれども $T$ は $S$ の部分集合ではないとき $S$ は $T$ の真部分集合であるといい, $S \subset T$ のように表記します。 部分集合を $\subset$, 真部分集合を $\subsetneq$ で表記する場合もあります。 お互いがお互いの部分集合であるとき, つまり含まれる元が完全に一致しているとき, ふたつの集合は等しいといい, $S = T$ のように表記します。
よく使われる集合にはお決まりの表記がありまして, 以下のような感じです。
- 自然数全体のなす集合 ... $\mathbb{N}$
- 整数全体のなす集合 ... $\mathbb{Z}$
- 有理数全体のなす集合 ... $\mathbb{Q}$
- 実数全体のなす集合 ... $\mathbb{R}$
- 複素数全体のなす集合 ... $\mathbb{C}$
おわかりかとは思いますが, これらは $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$ の関係をもちます。
ここに挙げたのはどれも無限の元を持つ集合ですが, 当然有限の集合もあります。
集合を定義するときに, その元をすべて数え上げる(途中や最後を省略するものを含む)こともできますが, かわりに元の条件を示すこともできます。 たとえば, $3$ 以上 $333$ 以下の自然数の集合は,
\{3, 4, 5, \ldots, 332, 333\}
のように書くこともできますが,
\{x \in \mathbb{N} \mid 3 \le x \le 333\}
のように書くこともできます。 この場合, 自然数に含まれる $x$ を集めた集合, ただし $3$ 以上 $333$ 以下のもの, と読み下せます。
元をひとつも含まない集合を空集合といい, 記号 $\varnothing$ で表記します。 $\varnothing$ はあらゆる集合の部分集合です。
濃度
元の個数のことを専門的には濃度とよびます。 なんでわざわざ別の用語を用意しているのかというと, 無限集合に対して個数を定義することはできないからです。 逆にいえば濃度は定義できます。
詳しくは後述しますが, 先に述べた集合について, その濃度は $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| < |\mathbb{R}| = |\mathbb{C}|$ の関係にあります。 自然数よりも整数のほうが多そうなのに不思議ですね。 $\mathbb{N}$ らの濃度を可算濃度といい, $\aleph_0$ や $\mathfrak{a}$ で表記します。 $\mathbb{R}$ らの濃度を連続体濃度といい, $\aleph$ や $\mathfrak{c}$, ないし $2^{\aleph_0}$ で表記します。 ちなみに $\aleph_0$ は無限濃度のなかで最小です。 言いかえると, 濃度が $\aleph_0$ 未満であれば, それは有限集合であるといえます。
合併
集合 $S$ と集合 $T$ の少なくともどちらか一方に含まれる元を集めた集合を $S$ と $T$ の合併あるいは和とよび, $S \cup T$ で表します。 たとえば,
\{1, 2, 3\} \cup \{2, 3, 4, 5\} = \{1, 2, 3, 4, 5\}
となります。
交叉
集合 $S$ と集合 $T$ の両方に含まれる元のみを集めた集合を $S$ と $T$ の交叉あるいは共通部分とよび, $S \cap T$ で表します。 たとえば,
\{1, 2, 3\} \cap \{2, 3, 4, 5\} = \{2, 3\}
差
集合 $S$ に含まれ, 集合 $T$ に含まれないような元を集めた集合を $S$ と $T$ の差あるいは相対補とよび, $S \setminus T$ で表します。 たとえば,
\{1, 2, 3\} \setminus \{2, 3, 4, 5\} = \{1\}
となります。
対称差
集合 $S$ と集合 $T$ のどちらか一方にのみ含まれるような元を集めた集合を $S$ と $T$ の対称差とよび, $S \xor T$ で表します。 たとえば,
\{1, 2, 3\} \xor \{2, 3, 4, 5\} = \{1, 4, 5\}
となります。
直積
集合 $S$ の元からひとつ, 集合 $T$ の元からひとつとった組を元として集めた集合を $S$ と $T$ の直積とよび, $S \times T$ で表します。 たとえば,
\{1, 2, 3\} \times \{2, 3, 4, 5\} = \{(1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 3), (3, 4), (3, 5)\}
となります。 この元である $(x, y)$ のことを順序対といい, プログラミングにおけるタプルに相当します。 よし, エンジニアリング要素を確保できたから Qiita の利用規約には反しないな!
直和
集合 $S$ の元と集合 $T$ の元を集めた集合を $S$ と $T$ の直和とよび, $S + T$ で表します。 合併との違いは $S$ と $T$ が交叉しないことを暗黙に述べていることです。 交叉しないことの保証のため, 添え字を使います。 たとえば, 添え字として単集合との直積を使うとすると,
\begin{aligned}
\{1, 2, 3\} + \{2, 3, 4, 5\} &= \{0\} \times \{1, 2, 3\} \cup \{1\} \times \{2, 3, 4, 5\} \\
&= \{(0, 1), (0, 2), (0, 3)\} \cup \{(1, 2), (1, 3), (1, 4), (1, 5)\} \\
&= \{(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (1, 4), (1, 5)\}
\end{aligned}
となります($0$ および $1$ は識別のために適当に用意されたものであることに注意。 どちらの集合の元かがわかればよい)。
補
集合 $S$ に含まれないような元を集めた集合を $S$ の補または絶対補とよび, $\complement S$ で表します。 ここで, 含まれない, とはどういう意味かを考える必要があります。 集合の補を考えるときは, 普遍集合あるいは全体集合とよばれる「考えるべきすべての元を含む集合」「$S$ のもととなったより大きな集合」が文脈上明らかになっている必要があります。
たとえば, 普遍集合が $\mathbb{N}$ なら,
\complement \{1, 2, 3\} = \{x \in \mathbb{N} \mid x \ne 1, 2, 3\}
となるでしょう。
冪
集合 $S$ の部分集合を集めた集合を $S$ の冪とよび, $2^S$ あるいは $\mathfrak{P}(S)$ で表します。 たとえば,
2^{\{1, 2, 3\}} = \{\varnothing, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}
となります。
ある集合 $S$ の濃度 $|S|$ が $n$ であるとき, その冪の濃度 $|2^S|$ は一般に $2^n$ になります。 $2^{\aleph_0}$ という表記は, つまり自然数の冪の濃度が実数の濃度に等しいということから来ているのですが, その証明は長くなるので省略します。
写像
写像とは関数のようなものです。 つまり, ある対象を別の対象に移し替える手続きです。 ただし, 部分関数や多価関数とよばれるものは基本的に写像には含みません。 これを言い換えると, 写像はある集合のそれぞれの元を, またある集合の元ただひとつに対応させます。 集合 $S$ のすべての元を集合 $T$ のただひとつの元に対応させる規則 $f$ が存在したとき, $f$ を始域 $S$ から終域 $T$ への写像といい,
f: S \to T
あるいは
S \xrightarrow{f} T
のように書きます。 また, $x$ に写像 $f$ を作用させると $y$ が得られるとき,
f: x \mapsto y
あるいは
x \xmapsto{f} y
のように書きます。 ここで $x$ が取りうる範囲を定義域, $y$ が取りうる範囲を値域といいます。 定義域は始域に(すべての元を対応させることからわかるように)一致するいっぽうで, 値域は終域の部分集合であるだけです。
初等数学において, 関数は同じ集合同士(多くは実数 $\mathbb{R}$ ですね)を結びつけるように扱う(実数関数と呼ばれていても, $f(x) = \sqrt{x}$ のように適切に定義域を制限する必要がある場合も多いですが)ことがほとんどでしたが, ことエンジニアの皆さんはまったく違う集合への写像というものを想像するのは難しくないはずです。
たとえば, 文字列の文字数を得る関数len(s)は,
\text{String} \xrightarrow{\mathtt{len}} \text{int}
なる写像とみなせます。
単射
移した先がかぶらないような写像を単射といいます。 より数学的に厳密な定義をすると,
x \ne y
であるならば
f(x) \ne f(y)
が常に成り立つとき, 写像 $f$ は単射です。
先程あげたlen(s)は, 別の文字列であっても同じ文字数となりうることから単射ではないことがわかります。
全射
どんな元にも移せるような写像を全射といいます。 より数学的に厳密な定義をすると,
y \in S
が終域 $S$ に含まれるとき,
f(x) = y
となる $x$ が常に存在するとき, 写像 $f$ は全射です。
先程あげたlen(s)は, 負の文字数をもつ文字列が存在しないことから全射ではないことがわかります。
しかし, もし符号なし整数型uintが存在すれば, 全射である写像 $\mathtt{len2}: \text{String} \to \text{uint}$ を定義することは可能です。 全射であるとは値域と終域が一致しているということと同値であり, 一見同じ規則に見えても終域が異なれば違う写像となるということです。 返り値の型が違えば別の関数である, それは当然だよね。 逆に言えば, どんな写像も終域を値域に制限すれば全射となります。
全単射
単射であり, かつ全射でもあるような写像を全単射といいます。 そのままですね。
全単射であるということは, 定義域と終域が写像によって一対一対応しているということです。 一対一対応しているので, 戻すこともできます。 写像 $f: S \to T$ が全単射であるならば, $x = f^{-1}\Bigl(f(x)\Bigr)$ となるような全単射な写像 $f^{-1}: T \to S$ が存在し, これを $f$ の逆写像といいます。
濃度と写像の関係
濃度の順序関係について, 単射な写像 $f: S \to T$ が定義できるとき, $|S| \le |T|$ と定義され, また全単射な写像 $f: S \to T$ が定義できるとき, $|S| = |T|$ と定義されます。 これは有限集合では当たり前なことですので, それを無限集合も含めて拡張しようというわけです。
これによると, たとえば
f(x) =
\begin{cases}
x \div 2 & \text{($x$ is even)} \\
-(x \div 2 + 1) & \text{($x$ is odd)}
\end{cases}
なる写像 $f: \mathbb{N} \to \mathbb{Z}$ は全単射です(ここで $\div$ はユークリッド除算。 $0$ から順に代入していけば $0, -1, 1, -2, 2, \ldots$ となります)。 なので, $|\mathbb{N}| = |\mathbb{Z}|$ といえます。 整数は自然数の $2$ 倍近くあるはずなのに。
ちなみに, 実際のところ, 濃度の演算規則(省略します)に従うと $2\aleph_0 = \aleph_0$ となります。 整数は自然数の $2$ 倍あるというのはそれほど間違いではありませんが, だからといって整数が自然数よりも多いとは言えないんですね。
逆に全単射な写像 $f: \mathbb{N} \to \mathbb{R}$ が作れないことはカントールの対角線論法(面倒なので省略します)からいえますので, $|\mathbb{N}| < |\mathbb{R}|$ となります。
自然数とビット演算
さて, 前置きがだいぶ長くなりました。
まず, 自然数とはどのようなものかを考えていきます。 ペアノシステムによると, 自然数は以下のようなもので構成されています。
- 最初の自然数 $0$
- ある自然数 $n$ の後者 $\suc n$
あらゆる自然数は「最初の自然数」から「後者」の繰り返しでしかありません。 これは直感的に納得していただけると思います。 最初の自然数として $1$ を選ぶこともできますが, この記事では $0$ を採用します。
一方でコンピュータでは数値はビット列によって表現されます。 ビット列といえば101101011101みたいなのを想像します。 が, ここではそういった「いかにもなビット列」は陽に扱わずにビット演算を定義します。
実のところ, ビット列とは「どの位置のビットが立っているか」ということにほかなりません。 つまり, 最下位ビットを $0$ とおき, その次を $\suc 0 = 1$, その次を $\suc 1 = 2$, というふうにおけば, 立っているビットを集めた集合と考えることができそうです。
このように考えると, どんな自然数も有限な自然数の集合と対応付けられそうです。 つまり, $\mathbb{N}$ の有限な部分集合全体がなす集合を
2^\mathbb{N}_{|S| < \aleph_0} \coloneqq \{S \in 2^\mathbb{N} \mid |S| < \aleph_0\}
と書くことにして,
\begin{aligned}
0 &\xmapsto{f} \varnothing \\
1 &\xmapsto{f} \{0\} \\
2 &\xmapsto{f} \{1\} \\
3 &\xmapsto{f} \{0, 1\} \\
4 &\xmapsto{f} \{2\} \\
5 &\xmapsto{f} \{0, 2\} \\
6 &\xmapsto{f} \{1, 2\} \\
7 &\xmapsto{f} \{0, 1, 2\} \\
\vdots
\end{aligned}
となるような全単射な写像 $f: \mathbb{N} \to 2^\mathbb{N}_{|S| < \aleph_0}$ が定義できるはずです。
そこで, 各ビット演算を以下のように定義します。
定義 自然数 $x, y \in \mathbb{N}$ に対する二項演算 Bitwise Or $\cup$, Bitwise And $\cap$, Bitwise Xor $\xor$ を以下のように定義する。
\begin{aligned} x \cup y &\coloneqq f^{-1}\Bigl(f(x) \cup f(y)\Bigr) \\ x \cap y &\coloneqq f^{-1}\Bigl(f(x) \cap f(y)\Bigr) \\ x \xor y &\coloneqq f^{-1}\Bigl(f(x) \xor f(y)\Bigr) \end{aligned}ただし, 写像 $f: \mathbb{N} \to 2^\mathbb{N}_{|S| < \aleph_0}$ を以下で定める。
f(x) \coloneqq \begin{cases} \varnothing & \text{($x = 0$)} \\ f(x') \cup \{m\} \setminus \{n \in \mathbb{N} \mid n < m\} \text{, where $m = \min(\complement f(x'))$} & \text{($x = \suc x')$} \end{cases}このとき, 逆写像 $f^{-1}: 2^\mathbb{N}_{|S| < \aleph_0} \to \mathbb{N}$ は以下のように定まる。
f^{-1}(S) = \sum_{n \in S} 2^n
「いかにもなビット列」「桁ごとの論理演算」などを陽に扱わずにビット演算を定義できました。 ちなみに写像 $f$ は,
f(x) \coloneqq
\begin{cases}
\varnothing & \text{($x = 0$)} \\
\begin{cases}
\{n + 1 \mid n \in f(x \div 2)\} & \text{($x$ is even)} \\
\{n + 1 \mid n \in f(x \div 2)\} \cup \{0\} & \text{($x$ is odd)}
\end{cases} & \text{(otherwise)}
\end{cases}
としても定義できます。 全射前者はインクリメントを, 後者は二進数への変換をイメージした書き方ですが, どちらが読みやすいでしょうかね?
ビット演算といえば NOT もありますが, これは自然数上では定義できません。 なぜなら, 補 $\complement S$ は $2^\mathbb{N}_{|S| < \aleph_0}$ 上で閉じていないからです。 普遍集合が $\mathbb{N}$ で, これは無限集合ですから, 有限集合の補は無限集合になってしまいます($2^\mathbb{N}_{|S| < \aleph_0}$ の定義は「有限な部分集合全体がなす集合」でしたよね)。 閉じていないのでは, $f^{-1}$ の定義域から外れてしまうので, 自然数に対応されないことがわかります。
符号なし整数とビット演算
しかし, コンピュータ上の自然数にあたる符号なし整数では NOT が定義されています。 これは, 実際のコンピュータで扱える整数型が固定長であることに由来します。
たとえば, 32 ビット符号なし整数の場合, 写像 $f$ の定義域は $\mathbb{N}_{x < 2^{32}}$ に制限されますので, 終域を $2^{\mathbb{N}_{x < 32}}$ に制限できます(ここで $\mathbb{N}_{x < n}$ は $\{x \in \mathbb{N} \mid x < n\}$ の意)。 この場合普遍集合は $\mathbb{N}_{x < 32}$ となり有限集合ですから, 補も $2^{\mathbb{N}_{x < 32}}$ で閉じます。 よって NOT が定義できます。
しかし, このように NOT を定義すると符号付き整数に対する NOT はこれとは違う値となり, 自然な延長とはみなせません。 ここが固定長整数型の辛いところです。
整数とビット演算
お次は整数について考察していきます。 日常的な感覚では, 整数は自然数に負の数を入れたものくらいの認識ですが, 当然まだ存在していない負の数を陽に扱っていては整数の定義はできないので, 数学的には別の定義があります。
まず, 自然数同士の直積 $\mathbb{N} \times \mathbb{N}$ を考えます。 この元はたとえば $(1, 0), (3, 5), (6, 6)$ などを含みます。
ここで, 同値関係 $(a, b) \sim (c, d) \Leftrightarrow d + a = b + c$ で割ります。 つまり, 右側を満たすような元同士は「等しい」とします。
その上でさらに, 自然数 $n$ を $(n, 0), (n + 1, 1), (n + 2, 2), \ldots$ に埋め込みます。 すると $n \ne 0$ について $(0, n), (1, n + 1), (2, n + 2), \ldots$ が余りますのでこれを $-n$ と表記するようにします。
和を $(a, b) + (c, d) = (a + c, b + d)$ で, 積を $(a, b)(c, d) = (ac + bd, da + bc)$ で入れて整数 $\mathbb{Z} \coloneqq (\mathbb{N} \times \mathbb{N})/\sim$ の完成です。
いきなりだと何が何だか分からないかもしれませんが, 有理数を同じように構成してみると上も理解できるかもしれません。 以下の記述では分数 $\frac{a}{b}$ が $(a, b)$ に対応しているということを頭に入れて読んでみてください。 少しはわかりやすいはずです。
整数と整数から $0$ を除いたものの直積 $\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$ を考えます。 この元はたとえば $(2, 1), (-4, 6), (-7, -7)$ などを含みます。
ここで, 同値関係 $(a, b) \sim (c, d) \Leftrightarrow ad = bc$ で割ります。 つまり, 右側を満たすような元同士は「等しい」とします。
その上でさらに, 整数 $x$ を $(x, 1), (2x, 2), (3x, 3), \ldots$ に埋め込みます。 すると互いに素な $a, b \ne 1$ について $(a, b), (2a, 2b), (3a, 3b) \ldots$ が余りますのでこれを $\frac{a}{b}$ と表記するようにします。
和を $(a, b) + (c, d) = (da + bc, bd)$, 積を $(a, b)(c, d) = (ac, bd)$ で入れて有理数 $\mathbb{Q} \coloneqq \Bigl(\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})\Bigr)/\sim$ の完成です。
整数に話を戻します。 現在のコンピュータでは, 負の数は一般に 2 の補数と呼ばれる手法によって表現されています。 2 の補数表現はオーバーフローを前提とした加法の成立などから実用上正当化されます。
2 の補数は以下のような手順で作れます。
- 得たい負の数の絶対値のビット列を用意する
- デクリメントする
- すべてのビットを反転させる
$-42$ を例にすると,
-
00101010... $42$ -
00101001... $41$ -
11010110... $-42$
これを手順として, 写像 $f$ の負の整数を定義域とする延長を考えることができます。 その値域は無限集合となってしまいますが, もとは有限であった集合の補です。 こういうものを補有限といいます。 $\mathbb{N}$ の補有限な部分集合全体がなす集合を
2^\mathbb{N}_{|\complement S| < \aleph_0} \coloneqq \{S \in 2^\mathbb{N} \mid |\complement S| < \aleph_0\}
と書くことにしましょう。 すると以下のように整数上でのビット演算を定義できます。
定義 整数 $x, y \in \mathbb{Z}$ に対する二項演算 Bitwise Or $\cup$, Bitwise And $\cap$, Bitwise Xor $\xor$ を以下のように定義する。
\begin{aligned} x \cup y &\coloneqq g^{-1}\Bigl(g(x) \cup g(y)\Bigr) \\ x \cap y &\coloneqq g^{-1}\Bigl(g(x) \cap g(y)\Bigr) \\ x \xor y &\coloneqq g^{-1}\Bigl(g(x) \xor g(y)\Bigr) \end{aligned}また, 整数 $x \in \mathbb{Z}$ に対する単項演算 Bitwise Not $\complement$ を以下のように定義する。
\complement x \coloneqq g^{-1}\Bigl(\complement g(x)\Bigr)ただし, 写像 $g: \mathbb{Z} \to 2^\mathbb{N}_{|S| < \aleph_0} \cup 2^\mathbb{N}_{|\complement S| < \aleph_0}$ を以下で定める。
g(x) \coloneqq \begin{cases} f(x) & \text{($x \ge 0$)} \\ \complement f(-x - 1) & \text{($x < 0$)} \end{cases}このとき, 逆写像 $g^{-1}: 2^\mathbb{N}_{|S| < \aleph_0} \cup 2^\mathbb{N}_{|\complement S| < \aleph_0} \to \mathbb{Z}$ は以下のように定まる。
g^{-1}(S) = \begin{cases} \displaystyle \sum_{n \in S} 2^n & \text{($|S| < \aleph_0$)} \\ -\left(\displaystyle \sum_{n \in \complement S} 2^n\right) - 1 & \text{($|S| = \aleph_0$)} \end{cases}
$g: \mathbb{N} \times \mathbb{N} \to 2^\mathbb{N}_{|S| < \aleph_0} \cup 2^\mathbb{N}_{|\complement S| < \aleph_0}$ を整数の構成から定義しようとすると以下のようになります。
g\Bigr((a, b)\Bigr) \coloneqq
\begin{cases}
f(n) & \text{($a = n, b = 0$)} \\
\complement f(n) & \text{($a = 0, b = \suc n$)} \\
g\Bigl((x, y)\Bigr) & \text{($a = \suc x, b = \suc y$)}\\
\end{cases}
g^{-1}(S) =
\begin{cases}
\left(\displaystyle \sum_{n \in S} 2^n, 0\right) & \text{($|S| < \aleph_0$)} \\
\left(0, \suc \displaystyle \sum_{n \in \complement S} 2^n\right) & \text{($|S| = \aleph_0$)}
\end{cases}
有理数とビット演算……?
自然数, 整数ときたら有理数に対してもビット演算を定義したいと考えるのは自然な考えですが, これは難しいと言わざるをえません。
ビット列の考え方でいけば, 有理数も固定小数点数として考えたくなります。 この場合小数点以下のビットは負の添字を持つと考えるのが自然でしょうから, $2^\mathbb{N}$ だったところが $2^\mathbb{Z}$ になりそうです。
たとえば, $\frac{1}{3}$ は(小数点以下のみを表示するとして)010101...となり, $\frac{2}{3}$ は(同様に)101010...となりますので,
\begin{aligned}
\frac{1}{3} &\xmapsto{h} \{-2, -4, -6, \ldots\} \\
\frac{2}{3} &\xmapsto{h} \{-1, -3, -5, \ldots\}
\end{aligned}
となるような写像 $h$ を考えることはできそうに思えます。 しかし, これの合併をとってみると,
h\left(\frac{1}{3}\right) \cup h\left(\frac{2}{3}\right) = \{-1, -2, -3, \ldots\}
となります。 これに対応する有理数が存在しないのです。 もちろん, 二進小数として $0.111... = 1$ なのですが, これを $1$ として認めてしまうと同じ元からふたつの像が生まれてしまうことになるので NG です。
言い換えると, $h$ の値域は合併や対称差で閉じていないのです。 残念です。
余談 - 自然数の構成からビット演算を考える
ところで自然数はどこからやってくるのでしょう。
現在の公理的集合論ではジョン・フォン・ノイマンの構成法と呼ばれる構成が主流となっています。 これは空集合と合併から自然数を構成します(空集合および合併の存在は現在の標準である ZF 公理系および ZFC 公理系で要請されます。 つまりまあこれらは空から降ってきたものと扱うということです)。
まず, 最初の自然数 $0$ を空集合で定義します。
0 \coloneqq \varnothing
そして, 後者 $\suc$ をそれ自身のみを元に持つ集合との合併とします。
\suc n \coloneqq n \cup \{n\}
こうして
\begin{aligned}
0 &= \varnothing \\
1 &= \{0\} \\
2 &= \{0, 1\} \\
3 &= \{0, 1, 2\} \\
4 &= \{0, 1, 2, 3\} \\
5 &= \{0, 1, 2, 3, 4\} \\
6 &= \{0, 1, 2, 3, 4, 5\} \\
7 &= \{0, 1, 2, 3, 4, 5, 6\} \\
\vdots
\end{aligned}
というように自然数が構成できます。 Swift や Ruby でこれをもとに自然数を構成している記事がありますのでぜひ読んでみてください。
でもペアノシステムの要請を満たすならば別にこの構成法でなくともよいわけです。 たとえば後者 $\suc$ を以下のように定義してみます。
\suc n \coloneqq n \cup \{m\} \setminus \{e \in \mathbb{N} \mid e < m\} \text{, where $m = \min \complement n$}
どこかで見たことありますね。 これによると,
\begin{aligned}
0 &= \varnothing \\
1 &= \{0\} \\
2 &= \{1\} \\
3 &= \{0, 1\} \\
4 &= \{2\} \\
5 &= \{0, 2\} \\
6 &= \{1, 2\} \\
7 &= \{0, 1, 2\} \\
\vdots
\end{aligned}
となり, この構成だと集合環になるので合併, 交叉, 対称差が閉じるし, それがそのままビット演算になります。 やったぜ。
え, 今から自然数を構成しようっていうのに $\mathbb{N}$ だの $\complement n$ だの使っていいのかですって? ま, まぁこれはあくまでも $0$ が含んでいるか調べて, 含んでいなければ入れて終了, 含まれていたら除いたあと $\suc$ で同じことを……という手続きを示したものとお考えください。 ほら, $\varepsilon - \delta$ 論法では $x \to \infty$ を手続きに読み替えるじゃないですか。
まあこの手続きが終了することの保証とか, ちゃんとペアノシステムを満たしているかの証明とかちゃんとやってないんでアレですが, こういう考え方もあるのではということで。
でもやっぱフォン・ノイマンの構成じゃないと $2 = \{0, 1\}$ ではなくなるので $2^\mathbb{N}$ みたいな冪の表記の正当性がなくなっちゃいますね。 元の個数がイコールもとの自然数になる強みはすごいです。
あと, これを採用した場合の順序数とかいらんことが気になり始めました。 そもそもこのたぬきそっち方面の知識ほとんどねえのにな。 $\omega$ が $\{0, 1, 2, \ldots \}$ なのはいいとして $\suc \omega$ は $\{\omega\}$ になるんでしょうか。 そんで $\suc (\suc \omega)$ は $\{0, \omega\}$? $\omega 2$ なら $\{0, 1, 2, \ldots, \omega\}$? いや自然数からの類推で行けばむしろ $\{1, 2, 3, \ldots\}$? $\omega$ おらんくなったけどいいの……? わけわかりませんね。 ライダー助けて。