BitAnd, BitOr, BitXor support for BigInt #13
Comments
|
It's not obvious how these operators should work with negative numbers without specifying their representation. Currently we store Ideally, I think we'd want this to behave similarly to the primitive integers, so we don't have surprises like We also don't support |
|
@cuviper If it helps: the reason for wanting this feature is that I'm working on a VM for a programming language. Said language exposes an integer type that under the hoods may or may not be a bigint, much like Ruby and Python do. I'd like to be able to perform operations such as Looking at https://github.com/ruby/ruby/blob/f92924923dd4d707abc8bf431d3c3e746fd8515a/bignum.c#L6417 it seems Ruby may emulate 2's-complement behaviour, but I can't tell for certain. Regarding the implementation for num-bigint, is there a place where this is done in a similar fashion that can perhaps be adopted for BitAnd & friends? I'm happy to provide a PR but I'm not very familiar with the internals of BigInt/BigUint so having something as a reference would be useful. |
|
I don't have a directly applicable example for you. Most of the time, the representation doesn't really matter. The fix in #8 is sort of related, but I don't think it's similar enough to help here. Currently FWIW, the "help wanted" label doesn't mean that I won't do it myself, just that I'm not working on it right now, so anyone else is welcome to try. If you think you can work it out, great! But don't worry about it if you can't. |
|
@cuviper I took a look around but I'm afraid this will be a bit out of my league. Would it at least help if I were to submit a PR adding some tests? That way at least some of the work is taken care of 😄 |
|
I'd love to have this feature as well! Being able to have an integer-like object with "infinite" leading 1s or 0s would help a lot in my use case in my project (bit masking). |
26: two's-complement logic operations on BigInt r=cuviper a=tspiteri This commit adds the following impls, giving results equivalent to what would be expected with two's complement. * `impl Not for BigInt` * `impl BitAnd<&BigInt> for BigInt`, `impl BitAndAssign<&BigInt> for BigInt` * `impl BitOr<&BigInt> for BigInt`, `impl BitOrAssign<&BigInt> for BigInt` * `impl BitXor<&BigInt> for BigInt`, `impl BitXorAssign<&BigInt> for BigInt` I also added some tests. There is most probably some room for optimization, but the bitwise operations all operate in place using a single pass. I did not add other implementations such as `impl BitAnd<BigInt> for BigInt`, those can be done later. Edit: Fixes #13
This adds support for arbitrary precision integers using the num-bigint crate. Regular integers overflow automatically into either a heap allocated i64 or a BigInt, depending on the size of the number. The code is a bit icky as it relies quite heavily on macros to reduce the number of functions necessary to make all this work. Bit shifting does use a few functions as they need to call each other recursively, something Rust macros can't do (as far as I could figure out at least). == num-bigint vs rug We're using num-bigint because it's easier to distribute, has a more pleasant API (compared to the "rug" crate) and has a permissive license. Performance might be worse compared to rug/GMP, but for the time being this should not pose any issues. == Bitwise operations Bitwise operations on big integers are currently not yet supported as num-bigint does not support these operators on the BigInt type. Once rust-num/num-bigint#13 has been solved we can add support for these operations.
New deps
Currently it seems that only BigUint implements BitAnd, BitOr, and BitXor. As a result it's not possible to perform such operations when using a BigInt. Would it be possible for these traits to be implemented for BigInt as well?
The text was updated successfully, but these errors were encountered: