std:bits — ビット演算

標準ライブラリモジュール (index.md)。本書中の裸の §N は本書の節を指す。言語の意味論は ../language-spec.md を参照。

import b := "std:bits" は Int のビット演算 6 関数を slot に持つ namespace object を b に束縛する。バイナリフォーマットやネットワークプロトコルの解読・構築 (フラグ抽出・バイト分解・固定長整数の組み立て) に使う。

std:math と同じく I/O を伴わず、純粋・同期 (Future を返さない)。

import b := "std:bits"

b.and(12, 10)          #> 8
b.or(12, 10)           #> 14
b.xor(12, 10)          #> 6
b.not(0)               #> -1
b.shift_left(1, 4)     #> 16
b.shift_right(-16, 2)  #> -4     (算術シフト = 符号拡張)

以下では import b := "std:bits" で束縛したものとして記す。

1. 意味論 — 任意精度・無限 2 の補数

Hikari の Int は任意精度整数 (language-spec.md §7.1。オーバーフローせず int64 を超える値も持てる)。std:bits の全演算はその値を無限桁の 2 の補数のビット列とみなして定義する。算術演算 (§7.1) と同様にビット幅の上限を設けない。

• 非負数は上位ビットが 0 で無限に続き、負数は上位ビットが 1 で無限に続く (2 の補数)。ゆえに b.and(-1, 255) == 255 (-1 は全ビット 1)、b.not(x) == -x - 1。
• and / or / xor / not はこのビット列同士の論理演算。int64 を超える値でもそのまま演算し、結果も任意精度 (b.shift_left(1, 100) は 2^100)。
• shift_left は左シフト。あふれる概念はなく、桁は無制限に伸びる (b.shift_left(1, 63) == 2^63、b.shift_left(x, k) == x * 2^k)。旧来の「mod 2^64 で符号ビットに回り込む」挙動は持たない。
• shift_right は算術右シフト (符号拡張)。b.shift_right(x, k) == floor(x / 2^k) で、負数の上位ビットは 1 で埋まる (b.shift_right(-16, 2) == -4、b.shift_right(-1, k) == -1)。k に上限は無い — 桁が減るだけなので、受け手の桁数を超える k は非負なら 0・負なら -1 にまとめる。
• 論理右シフトは持たない (無限 2 の補数では負数の上位が無限に 1 のため、幅を決めないと定義できない)。特定幅の下位ビットを取りたい場合はマスクと組み合わせる: b.and(b.shift_right(x, 56), 255) (下から 57〜64 ビット目の取り出し)。

2. 演算子ではなくモジュール関数である理由

Hikari は | をスロットリスト区切りの中核記号として使うため、ビット OR 演算子を構文に足すと衝突する。ゆえに演算子ではなくモジュール関数とする。root 名前空間を最小に保つ思想 (index.md) にも沿う。

3. slot 一覧

import b := "std:bits" で得られる closed namespace の slot:

本モジュールは効果を1 つも持たない（../language-spec.md §17.9）。

x は任意精度 Int を取り、結果も任意精度。shift_left の k は実用上の上限 (2^24。§4) までで、その範囲なら桁数に制限はない (b.shift_left(1, 100) は 2^100 を返す)。shift_right の k に上限は無い。

4. エラー

すべて回復可能エラー (Err) ではなく Error (バグ層、language-spec.md §16.2):

• 非 Int 引数 (全関数)
• シフト量 k が負 (shift_left / shift_right)
• shift_left の k が実現不能なほど巨大 (16777216 = 2^24 を超える)。左シフトは桁がその分だけ伸びるので、割り付けでプロセスごと落ちるより手前で止める。shift_right にこの上限は無い — 桁が減るだけで割り付けが要らず、答えは 0 か -1 にまとめられる

5. 持たないもの

• 論理右シフト (unsigned_shift_right 等)。幅を決めないと定義できない — Hikari の Int は任意精度で無限 2 の補数として振る舞うので、上位から詰める 0 の個数が定まらない。入れるなら幅を引数に取る形になり、それはこのモジュールが扱う「幅を持たない整数のビット演算」とは別の道具である。
• popcount / leading_zeros 等のビットカウント系（将来枠）。