How to do arithmetic operations with BitSlices?

user_7611589 0
Viewed 82

Using the bitvec crate, say I have two BitSlices:

let num1: &BitSlice = 10.view_bits::<Lsb0>();
let num2: &BitSlice = 9.view_bits::<Lsb0>();

Is there a way to run bit arithmetic operations such as num1 - num2 with these?

I have the limitation of working in a no-std environment and the bitslices can be rather big so I cannot convert them to numbers, do the operation and convert back to bit representation.

rust
2 Answers

bitvec used to include addition and subtraction, but they were removed in version 0.18. Also, there was never subtraction on BitSlice, only addition. Although it was mentioned they should be moved into a separate crate, I was unable to find such crate. So, you need to implement it yourself.

The easiest (although definitely not most efficient) way is to walk bit-by-bit and perform the operation.

For example, addition (adapted from the code in version 0.17.4):

/// May overflow.
pub fn add_assign(lhs: &mut BitSlice, rhs: &BitSlice) {
    fn add_with_carry(a: bool, b: bool, carry: bool) -> (bool, bool) {
        let result = u8::from(a) + u8::from(b) + u8::from(carry);
        ((result & 0b01) != 0, (result & 0b10) != 0)
    }

    let mut carry = false;
    let extended_rhs = rhs.iter().by_vals().rev().chain(core::iter::repeat(false));
    for (mut lhs_bit, rhs_bit) in lhs.iter_mut().rev().zip(extended_rhs) {
        (*lhs_bit, carry) = add_with_carry(*lhs_bit, rhs_bit, carry);
    }
}

Note that you cannot prevent overflow unless you can extend the slice, and that requires BitVec and allocation support.

user_78843050

For completeness, I will add my own function for subtraction as well:

pub fn subtract(lhs: &mut BitSlice, rhs: &BitSlice) {
    let mut borrow = false;
    for (mut l, r) in lhs
        .iter_mut()
        .rev()
        .zip(rhs.iter().by_vals().rev().chain(core::iter::repeat(false)))
    {
        if borrow {
            *l = !(*l);
            borrow = *l;
        }
        *l = match (*l, r) {
            (true, false) => true,
            (false, true) => {
                borrow = true;
                true
            }
            (_, _) => false,
        };
    }
}

I can make certain assumptions such as the bit order and lhs >= rhs for my use case, so if you are going to copy paste this code please consider such cases as well.

user_76115890
Related