Rustで立っているビットで一番端にあるものの位置を求めるプログラムが想定通り動かない

Question

こちらのページを参考に一番端の立っているビットの位置を求めるプログラムを実装しています。
参考にしているページはC#ですがRustで書き直しています。
https://ac-as.net/how-to-get-right-most-bit/

実装は上手くいってそうなんですけどある値を境にオーバーフローしてしまいます。
具体的には 1 ~ 6 までの値はオーバーフローせずに正常な値を得ることができます。
7 以降になるとオーバーフローしてしまいます。
どこか実装でミスをしているのか、そもそもアルゴリズムに対する理解が違うのか（6ビット区切りだからそもそも7桁以降は求められないのか？）
その他ネットで色々と情報を探しましたが手掛かりはありませんでした。
何かヒントがあれば教えていただけないでしょうか？

fn create_table() -> Vec<usize> {
    let mut table = vec![0usize; 64];
    let mut hash = 0x03F566ED27179461u64;
    for i in 0..64usize {
        table[(hash >> 58) as usize] = i;
        hash <<= 1;
    }
    table
}

fn count_bit(n: u64) -> usize {
    if n == 0 {
        return 64;
    }
    let y = ((n as i64) & -(n as i64)) as u64;
    let index = ((y*0x03F566ED27179461u64) >> 58) as u64;
    let table = create_table();
    table[index as usize]
}

fn main() {
    for i in 0..=7 {
        let n = 1u64 << i;
        println!("{}", count_bit(n)); // Error if i == 7
    }
}

エラーログ

0
1
2
3
4
5
6
thread 'main' panicked at 'attempt to multiply with overflow', src/main.rs:127:18
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

追記

なぜかpaizaの実行環境ではエラーにならず63まで正常に表示されました。。。
バージョンによる差異なのでしょうか。。。？

Paiza -> rustc 1.59.0
Local -> rustc 1.62.0

Comments

[hoshi-takanori]

掛け算がオーバーフローしてるようなので、wrapping_mul とか使うと良いかも。
https://qiita.com/garkimasera/items/c5e06de1a7c66aa7652a

[melian]

最適化オプション(-O)を付けてビルドしてください。

$ rustc -O ...

Understanding arithmetic overflow/underflows in Rust and Solana smart contracts
https://medium.com/coinmonks/understanding-arithmetic-overflow-underflows-in-rust-and-solana-smart-contracts-9f3c9802dc45

> Rust does not prevent Integer overflow/underflow
>
> However, in release (or optimization) mode, Rust silently ignores this behavior by default and computes two’s complement wrapping (e.g., 255+1 becomes 0 for an u8 integer).

[退会済みユーザー]

C# のタグがついてますが、関係ないので外してください。

[_Victorique__]

> SurferOnWww
元のコードがC#なので関係ないとは言えないので外しません。異議があるのであれば運営に直接お願いします。

Answer 1

attempt to multiply with overflow は、デバッグビルド環境においてオーバーフローが発生したときに発生するパニックです。
元の行番号が不明ですが、おそらく示されているコードでは16行目の y*0x03F566ED27179461u64 の箇所でオーバーフローしていると思われます。

Rustでは、掛け算で故意にオーバーフローさせて結果の上のビットを切り捨てる場合には、 wrapping_mul を使用します。
https://doc.rust-lang.org/std/primitive.i64.html#method.wrapping_mul
同様のメソッドが他の四則演算にもあります。

Comments

[_Victorique__]

C#とRustで動作が違うのを全く考えてませんでした。
上記メソッドを利用して上手く行きました！ありがとうございます！