在 Rust 中左移 (<<) 时如何惯用地测试溢出？

Question

对于大多数可能溢出的操作符，Rust 提供了一个检查版本。例如，要测试加法是否溢出，可以使用checked_add：

match 255u8.checked_add(1) {
    Some(_) => println!("no overflow"),
    None => println!("overflow!"),
}

这打印"overflow!". 还有一个checked_shl, 但根据文档，它只检查移位是否大于或等于self. 这意味着虽然这个：

match 255u8.checked_shl(8) {
    Some(val) => println!("{}", val),
    None => println!("overflow!"),
}

被捕获并打印"overflow!"，这是：

match 255u8.checked_shl(7) {
    Some(val) => println!("{}", val),
    None => println!("overflow!"),
}

只是打印128，显然没有捕捉到溢出。向左移动时检查任何类型溢出的正确方法是什么？

Answer 1

您可以进行互补右移（右移 8 - request_number_of_bits）并检查是否剩余 0。如果是这样，则意味着左移不会丢失任何位：

fn safe_shl(n: u8, shift_for: u8) -> Option<u8> {
    if n >> (8 - shift_for) != 0 {
        return None; // would lose some data
    }
    Some(n << shift_for)
}

人们还可以编写一个接受任何数字类型的通用版本，包括 bigint（并且适用于u8生成与上面完全相同的代码）：

use std::mem::size_of;
use std::ops::{Shl, Shr};

fn safe_shl<T>(n: T, shift_for: u32) -> Option<T>
where
    T: Default + Eq,
    for<'a> &'a T: Shl<u32, Output = T> + Shr<u32, Output = T>,
{
    let bits_in_t = size_of::<T>() as u32 * 8;
    let zero = T::default();
    if &n >> (bits_in_t - shift_for) != zero {
        return None; // would lose some data
    }
    Some(&n << shift_for)
}

操场

Answer 2

我不知道有什么惯用的方法可以做到这一点，但是像实现你自己的特质这样的方法会起作用：Playground

该算法基本上是检查数字中的前导零是否不少于移位大小

trait LossCheckedShift {
    fn loss_checked_shl(self, rhs: u32) -> Option<Self> 
        where Self: std::marker::Sized;
}

impl LossCheckedShift for u8 {
    fn loss_checked_shl(self, rhs: u32) -> Option<Self> {
        (rhs <= self.leading_zeros()).then_some(self << rhs)
    }
}

fn main() {
    match 255u8.loss_checked_shl(7) {
        Some(val) => println!("{}", val),
        None => println!("overflow!"), // <--
    } 
    
    match 127u8.loss_checked_shl(1) {
        Some(val) => println!("{}", val), // <--
        None => println!("overflow!"),
    }
    match 127u8.loss_checked_shl(2) {
        Some(val) => println!("{}", val),
        None => println!("overflow!"), // <--
    }
}