BigUint binary complement

Question

Example code:

use num_bigint::BigUint;
use num_traits::identities::One;

fn main() {
    // Example: 10001 (17) => 1110 (14)
    let n = BigUint::from(17u32);
    println!("{}", n);
    // BigUint doesn't support `!`
    //let n = !n;
    let mask = (BigUint::one() << n.bits()) - 1u32;
    let n = n ^ mask;
    println!("{}", n);
}

The above code is doing a binary complement of a BigUint using a bit mask. Questions:

1. Is there a better way to do the binary complement than with a mask? It seems BigUint doesn't include the ! operator (but the mask may be necessary anyway depending on how ! was defined).
2. If not is there a better way to generate the mask? (Caching masks helps, but can use lots of memory.)

---

More context with the problem I'm actually looking at: binary complement sequences

If you alternate multiplying by 3 and bit flipping a number some interesting sequences arise. Example starting with 3:

0. 3 (11b)  => 3*3 = 9 (1001b) => bit complement is 6 (0110b)
1. 6 (110b)
2. 13 (1101b)
3. 24 (11000b)
4. 55 (110111b)
5. 90 (1011010b)
6. 241 (11110001b)
7. 300 (100101100b)
8. 123 (1111011b)
9. 142 (10001110b)
11. 85 (1010101b)
12. 0 (0b)

One question is whether it reaches zero for all starting numbers or not. Some meander around for quite a while before reaching zero (425720 takes 87,037,147,316 iterations to reach 0). Being able to compute this efficiently can help in answering these questions. Mostly I'm learning a bit more rust with this though.

Answer 1

If you are looking for performance, num-bigint probably isn't the best choice. Everything that is really high-performance, though, seems to be GPL licensed.

Either way, here is a solution using the rug library, which directly supports !(not), and seems to be really fast:

use rug::{ops::NotAssign, Integer};

fn main() {
    // Example: 10001 (17) => 1110 (14)
    let mut n = Integer::from(17u32);
    println!("{}", n);
    n.not_assign();
    n.keep_bits_mut(n.significant_bits() - 1);
    println!("{}", n);
}

17
14

Note that not_assign also inverts the sign bit. We can remove that bit through the keep_bits_mut function.

---

For example, here is a version of your algorithm:

use rug::{ops::NotAssign, Integer};

fn step(n: &mut Integer) {
    *n *= 3;
    n.not_assign();
    n.keep_bits_mut(n.significant_bits() - 1);
}

fn main() {
    let mut n = Integer::from(3);
    println!("{}", n);
    while n != 0 {
        step(&mut n);
        println!("{}", n);
    }
}

3
6
13
24
55
90
241
300
123
142
85
0

Answer 2

The best solution is probably to just do it yourself. You perform an allocation each time you create a BigUint which really slows down your program. Since we are not doing complex math, we can simplify most of this to a couple bitwise operations.

After a little bit of tinkering, here is how I implemented it. For convenience, I used the unstable nightly feature bigint_helper_methods to allow for the carrying_add function. This helped simplify the addition process.

#[derive(Debug)]
pub struct BigUintHelper {
    words: Vec<u64>,
}

impl BigUintHelper {
    pub fn mul3_invert(&mut self) {
        let len = self.words.len();

        // Multiply everything by 3 by adding it to itself with a bit shift
        let mut carry = false;
        let mut prev_bit = 0;
        for word in &mut self.words[..len - 1] {
            let previous = *word;

            // Perform the addition operation
            let (next, next_carry) = previous.carrying_add((previous << 1) | prev_bit, carry);

            // Reset carried values for next round
            prev_bit = previous >> (u64::BITS - 1);
            carry = next_carry;

            // Invert the result as we go to avoid needing another pass
            *word = !next;
        }

        // Perform the last word seperatly since we may need to do the invert differently
        let previous = self.words[len - 1];
        let (next, next_carry) = previous.carrying_add((previous << 1) | prev_bit, carry);


        // Extra word from the combination of the carry bits
        match next_carry as u64 + (previous >> (u64::BITS - 1)) {
            0 => {
                // The carry was 0 so we do the normal process
                self.words[len - 1] = invert_bits(next);
                self.cleanup_end();
            }
            1 => {
                self.words[len - 1] = !next;
                // invert_bits(1) = 0
                self.cleanup_end();
            }
            2 => {
                self.words[len - 1] = !next;
                // invert_bits(2) = 1
                self.words.push(1);
            }
            _ => unreachable!(),
        }
    }

    /// Remove any high order words without any bits
    #[inline(always)]
    fn cleanup_end(&mut self) {
        while let Some(x) = self.words.pop() {
            if x != 0 {
                self.words.push(x);
                break;
            }
        }
    }

    /// Count how many rounds it takes to convert this value to 0.
    pub fn count_rounds(&mut self) -> u64 {
        let mut rounds = 0;

        while !self.words.is_empty() {
            self.mul3_invert();
            rounds += 1;
        }

        rounds
    }
}


impl From<u64> for BigUintHelper {
    fn from(x: u64) -> Self {
        BigUintHelper {
            words: vec![x],
        }
    }
}

#[inline(always)]
const fn invert_bits(x: u64) -> u64 {
    match x.leading_zeros() {
        0 => !x,
        y => ((1u64 << (u64::BITS - y)) - 1) ^ x
    }
}

Rust Playground