Enhancements for parity with primitives

[Kixiron]

For parity with primitives and other standard types, the following features would be amazing

• [ ] core::ops::Not and std::ops::Not for BigUint
• [ ] Checked operations for BigUint, e.g. checked_add
• [ ] BigInt/BigUint with_capacity plus a method to determine the current int's capacity

[Kixiron]

Additionally, none of the checked_ operation variants are implemented for BigUint

[cuviper]

core::ops::Not and std::ops::Not for BigUint

Note, those traits are one and the same, defined in core and re-exported in std.

What would you want this to do with leading zeros? For a fixed-width size, that's no problem, just make them all ones, but BigUint is semantically infinite. We do have Not for BigInt because we can use negative values as if it were 2's complement, with an infinite prefix of ones. There's prior art for this in Python bitwise operators, where ~x is -x - 1.

Another option is to ignore leading zeros and just flip up to the most-significant bit, but that means the round trip !!x won't return to the same value. We could also flip the bits of whatever big-digits are currently allocated, but that exposes the internal digit size which may be different on some targets. We also have an invariant to never have 0 in the most-significant digit, but that would again break the !!x round trip if we trim that.

Checked operations for BigUint, e.g. checked_add

It does implement the trait CheckedAdd etc., but it just doesn't have the same inherent methods that you can use without importing the trait, like BigInt does. They're mostly useless except for checked_div dividing by 0, although I guess checked_sub also avoids negative cases for BigUint. For addition and multiplication, the only reason to have these is for generic code taking T: CheckedAdd, which doesn't need the inherent method at all.

BigInt/BigUint with_capacity plus a method to determine the current int's capacity

This doesn't fit the subject of "parity with primitives"...

I have thought about adding capacity methods, sort of related to #98. I would want this to be either in bits or bytes though, not exposing the internal digit size.

[Kixiron]

Sorry it took me so long to respond, I've been busy.

What would you want this to do with leading zeros?

I honestly didn't think this would have been as complex of a task as it turned out to be, but (forgive me if this is just plain stupid) couldn't iterating over the internal digits and applying Not to them suffice? Ex.

for digit in self.data.iter_mut() {
    *digit = !*digit;
}

It does implement the trait CheckedAdd etc.

I'm sorry, I didn't see those!

This doesn't fit the subject of "parity with primitives"...

Forgive me, I was trying to make a title that fit the more general scope of the issue

I have thought about adding capacity methods [..] not exposing the internal digit size.

However it's exposed is fine, as long as there's a way to pre-allocate another Big{U}Int

Thank you for taking the time to respond!

[cuviper]

couldn't iterating over the internal digits and applying Not to them suffice?

In the current master branch, the internal digit size varies by target for efficient computation, u32 on 32-bit targets and u64 on 64-bit, and this is considered an implementation detail that may yet change. But even as-is, that means !BigUint::one() as you suggest would return 0xfffffffe on 32-bit targets and 0xfffffffffffffffe on 64-bit. That seems bad.

We also don't keep any leading zeros, so BigUint::zero() is completely empty. Thus, if we just applied Not to all digits, !BigUint::zero() would still be zero!

For the round-trip problem, take a concrete example like let x = (BigUint::one() << 256) - 1u32 -- in binary that's 256 ones, and in digits that will be a size-dependent number of 0xff...ff digits. If we Not this digit-by-digit, they would all turn zero, and then for our no-leading-zeros invariant we'd trim it to an empty vector. If we Not it again, there are no digits left to change, so it remains zero. That means we have x != !!x, which would be pretty surprising.