2026-10-17
lut_count.rs
fn functions(k: u32) -> u64 {
2u64.pow(2).pow(k)
}
fn main() {
for k in 1..=4 {
println!("{k}: {}", functions(k));
}
}
0 か 1 の値を k 個受け取って 0 か 1 を返す関数を、k 変数のブール関数(Boolean function)といいます。入力の組は 2^k 通りあり、そのそれぞれに 0 か 1 を割り当てる方法の数だけ関数があるので、個数は 2^(2^k) です(^ は累乗)。functions(k) はこの個数を返すつもりの関数で、入力は main の k = 1 から 4 です。いまは 1: 4、2: 16、3: 64、4: 256 の4行が出ます。本来の出力は 1: 4、2: 16、3: 256、4: 65536 です。
Answer
Wrong
2u64.pow(2).pow(k)
メソッド呼び出しは左から順に評価されるので、この式は 2u64.pow(2) の 4 を先に作り、それを k 乗します。計算しているのは (2^2)^k = 4^k で、数学の 2^2^k が表す 2^(2^k) ではありません。4^k は 2^(2k) なので、2k と 2^k が等しい k = 1 と 2 では正しい値と一致し、k = 3 から小さすぎる値になります。
Right
2u64.pow(2u32.pow(k))
指数の 2^k を先に計算して、それを pow の引数に渡します。pow の指数は u32 なので、指数側は 2u32.pow(k) で作ります。右側の累乗を括弧の内側に置く形にすると、累乗の右結合がそのままコードの入れ子になります。k = 6 では 2^64 になって u64 に収まらず、デバッグビルドではオーバーフローの panic で止まります。