概要

$\pm 1$-RMQ 問題に代表されるように、桁数付きのビットパターンをキーにした前計算テーブルが必要なことがよくありますが、そのまま整数の $2$ 進展開と解釈してしまうと長さの違いが同一視されてしまいます。これを回避するキレイな方法をご紹介し、また関連する話題をいくつかご紹介します。

結論

結論から言うと、先頭に 1 を付けるのが良いと思います。この記事ではこれを浮動小数点数の仮数部の表現に倣って hidden-bit base-$2$ と呼びます。これは別のよく知られた記法 bijective base-$2$（説明中のリンク参照）と非常によく似ています。というわけでこれら 3 種類の記数法を比較してみましょう。

Base-$2$: 2 種類の digits 0, 1 を用いた通常の $2$ 進展開。$0$ は空文字列。
Bijective base-$2$: 2 種類の digits 1, 2を用いた $2$ 進展開。Bijective numeration の一種。$0$ は空文字列。
Hidden-bit base-$2$: 2 種類の digits 0, 1 を用いた通常の $2$ 進展開から先頭の 1 を除いたもの。$1$ が空文字列。$0$ はどの表現にも対応しない。

非常に単純な方法ですが、これでほぼ無駄がなく、かつ shortlex 順序を保った形になって非常に扱いやすいことが、次の表をご覧いただくと分かると思います。諸々の変換もビット演算等でラクラクです。正整数を浮動小数点数で表した場合は指数部に桁数が入るのでその点も似ていますね。

base-$2$ と bijective base-$2$ 、hidden-bit base-$2$ の比較表

関連する話題

いわゆる「一進法」

1, 11, 111, ... のような表記は一進法（unary numeral system）と呼ばれていますが、実際には bijective numeration の一種なので、bijective base-1 です。

いわゆる「Excel 進法」

ツールを作るときに独自実装しようとしてバグらせるのを何度も見たやつです。これも bijective base 26 です。

悲劇を繰り返されないためにコード置いておきますね。A が $1$ に対応することに注意です。（この仕様を変えたい場合は頑張ってください。ファイト！エイ！エイ！）

fn encode(mut a: usize) -> String {
    let mut result = Vec::new();
    while a != 0 {
        a -= 1;
        result.push((a % 26) as u8 + b'A');
        a /= 26;
    }
    result.reverse();
    String::from_utf8(result).unwrap()
}


fn decode(s: &str) -> usize {
    let mut result = 0;
    for &c in s.as_bytes() {
        result *= 26;
        result += usize::from(c - b'A' + 1);
    }
    result
}

浮動小数点数

IEEE754 倍精度浮動小数点数を前提にお話します。たとえば binaryconvert.com を動かすとわかるように、$70 = 64 + 4 + 2 = 2 ^ 6 \cdot (1 + 2 ^ { -4 } + 2 ^ { -5 })$ は次のようなビット列で表現されます。

01000000 01010001 10000000 00000000
00000000 00000000 00000000 00000000

符号ビットが 0（$+$）、指数部が 10000000101（$1023$ の offset があるので $1024 + 4 + 1 - 1023 = 6$）、仮数部が 0001100000000000000000000000000000000000000000000000 （hidden-bit 表現なので $1 + 2 ^ { -4 } + 2 ^ { -5 }$）です。