Rust中如何对num_bigint::BigInt执行右位移操作？

问题原因 #

Rust的num_bigint::BigInt实现的>>和>>=运算符，要求位移位数必须是usize类型，而非BigInt类型。你遇到的no implementation for BigInt >> BigInt``错误，就是因为尝试用另一个BigInt作为位移参数导致的。

针对米勒拉宾测试场景的解决方案 #

你的场景中需要将EC（候选素数-1）反复右移1位直到它变为奇数，这本质是不断除以2，以下两种方式都能实现需求：

方式1：使用>>运算符（直接传入usize类型位移量） #

直接传入字面量1（会自动推断为usize）即可满足右移1位的需求：

use num_bigint::BigInt;
use num_traits::{One, Zero};

let mut ec = candidate.clone() - BigInt::one();
while &ec % 2 == BigInt::zero() {
    ec = ec >> 1; // 1是usize类型，符合运算符要求
}

方式2：使用除法操作（逻辑更直观） #

右移1位等价于除以2，也可以直接用/运算符实现：

use num_bigint::BigInt;
use num_traits::{One, Zero};

let mut ec = candidate.clone() - BigInt::one();
while &ec % 2 == BigInt::zero() {
    ec = ec / 2; // 除以2和右移1位效果完全一致
}

通用情况：位移位数为BigInt的处理 #

如果你的场景中位移位数确实是BigInt类型（非固定值1），可以按以下逻辑处理：

• 若位移量小于等于usize::MAX，将其转换为usize后使用>>或shr方法；
• 若位移量超过usize范围，由于BigInt的二进制位数有限，超过自身位数的右移结果必然是0，直接返回BigInt::zero()即可。

示例代码：

use num_bigint::BigInt;
use num_traits::ToPrimitive;

fn big_shr(mut num: BigInt, shift: &BigInt) -> BigInt {
    match shift.to_usize() {
        Some(s) => num >> s,
        None => BigInt::zero(),
    }
}

内容的提问来源于stack exchange，提问作者Poseidon