コマンドには整数のビット演算が存在しないため、ビット演算を行いたい場合には1ビットずつ処理を行う必要があります。
素数積による疑似ビットベクトル表現を用いることで、ビットの密度を犠牲にして一部のビット演算を高速に行うことができます。
以下のように、素数の積を用いて長さ8のビットベクトルを表現することができます。
下位 $i$ 番目のビットを $b_i$ 、 $3$ から数えて $i$ 番目の素数を $p_i$ とします。
$$
\begin{align*}
&\prod_{i=0}^{7} (b_i \ ? \ p_i : 1) \\\
= \ &
(b_7 \ ? \ p_7 : 1)
(b_6 \ ? \ p_6 : 1)
(b_5 \ ? \ p_5 : 1)
(b_4 \ ? \ p_4 : 1)
(b_3 \ ? \ p_3 : 1)
(b_2 \ ? \ p_2 : 1)
(b_1 \ ? \ p_1 : 1)
(b_0 \ ? \ p_0 : 1)
1 \\\
= \ &
(b_7 \ ? \ 23 : 1)
(b_6 \ ? \ 19 : 1)
(b_5 \ ? \ 17 : 1)
(b_4 \ ? \ 13 : 1)
(b_3 \ ? \ 11 : 1)
(b_2 \ ? \ 7 : 1)
(b_1 \ ? \ 5 : 1)
(b_0 \ ? \ 3 : 1)
1
\end{align*}
$$
例えば、ビットベクトル $\texttt{10101011}$ は
$$
\begin{align*}
&
(1 \ ? \ 23 : 1)
(0 \ ? \ 19 : 1)
(1 \ ? \ 17 : 1)
(0 \ ? \ 13 : 1)
(1 \ ? \ 11 : 1)
(0 \ ? \ 7 : 1)
(1 \ ? \ 5 : 1)
(1 \ ? \ 3 : 1)
1 \\\
= \ & 23 * 17 * 11 * 5 * 3 * 1 \\\
= \ & 64515
\end{align*}
$$
と表現されます。
最大のビットベクトルは $\texttt{11111111}$ でその表現は $23 * 19 * 17 * 13 * 11 * 7 * 5 * 3 * 1 = 111546435$ です。
32ビット符号付き整数の最大値は $2^{31} - 1 = 2147483647 \ (\ge 111546435)$ なので、全てのビットベクトルは32ビット符号付き整数で表現できます。
9番目のビットとして素数 $29$ を追加すると最大値が $29 * 23 * 19 * 17 * 13 * 11 * 7 * 5 * 3 * 1 = 3234846615 \ (\ge 2147483647)$ になり、32ビット符号付き整数では表現できなくなります。
素数積による疑似ビットベクトル表現 $a$ で $\texttt{11111111}$ を割ることで~aを計算することができます。
例えば、 $a = \texttt{10101011}$ とすると、
$$
\begin{align*}
& \texttt{11111111} \ / \ \texttt{10101011} \\\
= \ & p_7 p_6 p_5 p_4 p_3 p_2 p_1 p_0 \ / \ p_7 p_5 p_3 p_1 p_0 \\\
= \ & p_6 p_4 p_2 \\\
= \ & \texttt{01010100}
\end{align*}
$$
素数積による疑似ビットベクトル表現 $a$ と $b$ について、 $a$ と $b$ の最大公約数 $gcd(a, b)$ を計算することでa & bを計算することができます。
例えば、 $a = \texttt{10101011}$ 、 $b = \texttt{01110101}$ とすると、
$$
\begin{align*}
& \mathit{gcd}(\texttt{10101011}, \texttt{01110101}) \\\
= \ & \mathit{gcd}(p_7 p_5 p_3 p_1 p_0, p_6 p_5 p_4 p_2 p_0) \\\
= \ & p_5 p_0 \\\
= \ & \texttt{00100001}
\end{align*}
$$
素数積による疑似ビットベクトル表現 $a$ と $b$ について、 $a$ と $b$ の最小公倍数 $lcm(a, b)$ を計算することでa | bを計算することができます。
例えば、 $a = \texttt{10101011}$ 、 $b = \texttt{01110000}$ とすると、
$$
\begin{align*}
& \mathit{lcm}(\texttt{10101011}, \texttt{01110000}) \\\
= \ & \mathit{lcm}(p_7 p_5 p_3 p_1 p_0, p_6 p_5 p_4) \\\
= \ & p_7 p_6 p_5 p_4 p_3 p_1 p_0 \\\
= \ & \texttt{11111011}
\end{align*}
$$
素数積による疑似ビットベクトル表現 $a$ と $b$ について、 $a$ と $b$ の最小公倍数 $lcm(a, b)$ を $a$ と $b$ の最大公約数 $gcd(a, b)$ で割ることでa ^ bを計算することができます。
例えば、 $a = \texttt{00000011}$ 、 $b = \texttt{00000101}$ とすると、
$$
\begin{align*}
& \mathit{lcm}(\texttt{00000011}, \texttt{00000101}) / \mathit{gcd}(\texttt{00000011}, \texttt{00000101}) \\\
= \ & \mathit{lcm}(p_1 p_0, p_2 p_0) / \mathit{gcd}(p_1 p_0, p_2 p_0) \\\
= \ & p_2 p_1 p_0 / p_0 \\\
= \ & p_2 p_1 \\\
= \ & \texttt{00000110}
\end{align*}
$$
素数積による疑似ビットベクトル表現 $a$ と $b$ について、 $a$ が $b$ で割り切れるかどうか調べることでa & b == bを計算することができます。
例えば、 $a = \texttt{10101011}$ 、 $b = \texttt{00001011}$ とすると、
$$
\begin{align*}
& \texttt{10101011} \ \% \ \texttt{00001011} \\\
= \ & p_7 p_5 p_3 p_1 p_0 \ \% \ p_3 p_1 p_0 \\\
= \ & 0
\end{align*}
$$
結果が $0$ になったので、a & b == bです。
一方、 $a = \texttt{10101011}$ 、 $b = \texttt{00001111}$ とすると、
$$
\begin{align*}
& \texttt{10101011} \ \% \ \texttt{00001111} \\\
= \ & p_7 p_5 p_3 p_1 p_0 \ \% \ p_3 p_2 p_1 p_0 \\\
= \ & 990
\end{align*}
$$
結果が $0$ 以外になったので、a & b == bではありません。
定数によるビットマスクテスト(a & B == B) 先述したビットマスクテストでは $a$ に対して%=演算を行う必要があり、 $a$ の値が変化してしまいます。
そのため、 $a$ の値を保持したい場合、一旦別のスコアに $a$ をコピーする必要があります。
ビットマスク $B$ が定数である場合、 $B$ の逆数を用いて $a$ を保持したままビットマスクテストを行うことができます。
$B$ の逆数とは $B B^{-1} = 1$ を満たす $B^{-1}$ のことです。
32ビット整数の場合、以下のようにニュートン法を用いて $B^{-1}$ を事前計算することができます。1 全てのビットベクトルと逆数の対応表 )
const fn inverse ( x : i32 ) -> i32 {
const fn f ( x : i32 , y : i32 ) -> i32 {
y. wrapping_mul ( 2 . wrapping_sub ( y. wrapping_mul ( x) ) )
}
f ( x, f ( x, f ( x, 3i32 . wrapping_mul ( x) ^ 2 ) ) )
} $a$ が $B$ で割り切れる場合かつその場合に限り、 $a B^{-1} \in [1, p_7p_6p_5p_4p_3p_2p_1p_0 / B]$ が成立します。
また、 $a B^{-1} B = a$ が成立します。
そのため、以下のような疑似コードで $a$ を保持したままビットマスクテストを行うことができます。
$$
\begin{align*}
& a \ \texttt{*=} \ B^{-1} \\\
& \texttt{if} \ a \in [1, p_7p_6p_5p_4p_3p_2p_1p_0 / B] \\\
& \quad \texttt{then} \ \text{\{\texttt{a \& B == B} の場合の処理\}} \\\
& \quad \texttt{else} \ \text{\{\texttt{a \& B != B} の場合の処理\}} \\\
& a \ \texttt{*=} \ B
\end{align*}
$$
$B^{-1}, p_7p_6p_5p_4p_3p_2p_1p_0 / B, B$ は全て定数です。
$a$ の特定のビット $p_k$ が $\texttt{1}$ であることが分かれば、 $a$ を $p_k$ で割ることでそれを $\texttt{0}$ にすることができます。
同様に、 $a$ の特定のビット $p_k$ が $\texttt{0}$ であることが分かれば、 $a$ に $p_k$ を掛けることでそれを $\texttt{1}$ にすることができます。
素数の $2$ を用いることで、疑似ビットベクトル表現のビット数を1増やすことができます。
ただし、 $2$ には逆数が存在しないため定数によるビットマスクテストにおいて $2$ に対応するビットを同様に調べることはできなくなります。
また、 $-1$ を用いることでも疑似ビットベクトル表現のビット数を1増やすことができますが、符号の取り扱いには注意が必要です。
