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

Question

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

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

这会打印 "overflow!"。还有一个checked_shl，但是根据the documentation它只检查移位是否大于或等于self中的位数。这意味着虽然这样：

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

被捕获并打印 "overflow!", This:

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

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

Answer 1

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

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

#![feature(bool_to_option)]

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)
        // in stable Rust
        // if rhs <= self.leading_zeros() { Some(self << rhs) }
        // else { None }
    }
}

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!"), // <--
    }
}

Answer 2

您可以做一个补充 right-shift（right-shift 乘以 8 - requested_number_of_bits）并检查是否还有 0。如果是这样，则意味着 left-shifting:

不会丢失任何位

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)
}

也可以编写一个通用版本，它接受任何数字类型，包括 bigints（并且应用于 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)
}

Playground

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

How to Idiomatically Test for Overflow when Shifting Left (<<) in Rust?

integer-overflow

bit-shift

logical-operators

rust