impl Not for BigUint

[Lichtso]

https://docs.rs/num-bigint/0.3.1/num_bigint/struct.BigInt.html?search=not

Seems like there is only an implementation of not for BigInt.

[cuviper]

Conceptually, BigUint has infinite leading zeros. There's no clear answer how far we should flip bits for Not. Even if we just flipped the current number of inner BigDigit (which is arch-dependent), this may be inconsistent in the round trip, !!x, when we uphold the invariant that leading zero digits are trimmed. For that matter, BigUint::zero() has no digits at all, so would its not() also be zero?

With BigInt, we conceptually have infinite leading bits either way, zeros for positive and ones for negative, like 2's complement. So we have a way to implement Not that is consistent with signed primitive integers. That is, 2's complement -x = !x + 1, so !x = -x - 1.

[Lichtso]

In theory one could define the MSB to be implicitly extended towards infinity (like sign extension).
So 0 ... 0001
would be inverted to 1 ... 1110
and back to 0 ... 0001.

But that probably breaks a lot of the other assumptions and operations.

[cuviper]

Do you have a use for Not on a BigUint? Perhaps we can solve that another way. Maybe we should also add my explanation or similar to the docs somewhere.