🦀

Rustで整数を表すのに必要なビット数を求める

に公開
Rust
tech

はじめに

この記事は、RustでPythonのint.bit_length()のように整数を表すのに必要なビット数を求める方法について書いたものです。

自然数の場合

整数nがn > 0であるとき、n.ilog2() + 1でnを表すのに必要なビット数を求めることができます。

let answer: u8 = 42;
assert_eq!(answer.ilog2() + 1, 6);

ilog2()はn \leqq 0であるときはパニックします。
n \leqq 0な可能性があるときは、Option<T>を返すchecked_ilog2()を利用することでパニックを避けることができます。

let answer: u8 = 42;
assert_eq!(answer.checked_ilog2().map(|n| n + 1), Some(6));
assert!(0_u8.checked_ilog2().is_none());

ilog2やchecked_ilog2はRust 1.67.0で安定化されました。
それ以前のバージョンでは、以下のようにその型のビット数（32）からleading_zeros()で得た値を二進数で表現したときの先頭の0の数を引くことで同様の結果を求められます。

let answer: u32 = 42;
let old = 32 - answer.leading_zeros();
let new = answer.ilog2() + 1;
assert_eq!(old, new);

32というマジックナンバーは、Rust 1.53.0で安定化されたその型のビット数を表すBITS関連定数で置き換えることができます。

n = 0も含めた全ての符号無し整数で値を表すのに必要なビット数は、以下の方法で求めることができます。

let n = u32::MIN;
assert_eq!(n.checked_ilog2().map_or(0, |n| n + 1), 0);

符号付き整数で符号ビットも含めて値を表すのに必要なビット数は、最初の方法を以下のように修正することで求めることができます。

let answer: i8 = 42;
-assert_eq!(answer.ilog2() + 1, 6);
+assert_eq!(answer.ilog2() + 2, 7);

負の整数の場合

Pythonのint.bit_length()のように符号を除いた負の整数nを表すのに必要なビット数を求めたいとき（-37のときは37）、n \neq 0であるときはn.unsigned_abs().ilog2() + 1で求めることができます。

let n: i32 = -37;
assert_eq!(n.unsigned_abs().ilog2() + 1, 6);

殆どの場合はabs()で問題ないですが、nがi32::MINなどのその型の最小値のときにオーバーフローが発生するので、unsigned_abs()を使う方が安全です。

符号ビットも含めた負の整数nを表すのに必要なビット数を求めたいとき、n < -1であるときは(n + 1).abs().ilog2() + 2で求めることができます。

let n: i16 = -128;
assert_eq!((n + 1).abs().ilog2() + 2, 8);

let m: i16 = -129;
assert_eq!((m + 1).abs().ilog2() + 2, 9);

n \geqq -1な可能性があるときは、checked_ilog2()を利用することで自然数の場合と同様にパニックを避けることができます。

n = 0とn = -1も含めた全ての符号付き整数で値を表すのに必要なビット数は、以下の方法で求めることができます。

let n: i32 = -1;
let bit_width = match n {
    0 | -1 => 0,
    n if n.is_positive() => n.ilog2() + 2,
    n => (n + 1).abs().ilog2() + 2,
};
assert_eq!(bit_width, 0);

終わりに

紹介した方法だとn = 0またはn = -1のときは必要なビット数を求めることができないので、これらの場合にも対応したもっと良い方法があるかもしれません。

GitHubで編集を提案

Discussion