BigUint should have count_ones() and similar methods

[BartMassey]

I needed BigUint::count_ones() for a project, so I implemented it in terms of to_u32_digits().

fn count_ones(b: BigUint) -> u32 {
    b
        .to_u32_digits()
        .into_iter()
	.map(|d| d.count_ones())
        .sum()
}

But now I'm relying on the optimizer to clean up my code, plus the implementation should probably return u64 because it's pretty easily possible to have more than 4 billion ones in a BigUint so it's buggy. :-)

I'd be happy to put together some kind of pull request if there's some interest in one.

[cuviper]

The iterators in #158 will at least let you do that without creating a temporary Vec, but there will still be some translation from the internal digit size, which is extraneous for your task. Internally iterating self.data would be ideal, so yes, I'm open to a pull request for BigUint::count_ones(&self) -> u64.

A harder question is whether we should do anything for BigInt, since negative numbers conceptually have an infinite prefix of 1s in twos-complement (though we store sign+magnitude). We could count ones in the magnitude instead, but I think it would be unfortunate to have such different semantics from iN::count_ones. I suppose folks can use bigint.magnitude().count_ones() if that's what they want.

RE: "and similar methods": For count_zeros, I guess we could define that as only counting less than the MSB 1. For leading_zeros we'd have the same problem of the infinite prefix, but BigUint::leading_ones should be okay. We do have trailing_zeros already, and fortunately that is even consistent between twos-complement and the magnitude. I think that would be mostly true for trailing_ones too, but BigInt == -1 would need to be an exception.

[tczajka]

It's not true for trailing_ones, e.g. (-3).trailing_ones() == 1 while 3.trailing_ones() == 2.

[cuviper]

@tczajka Ah, you're right, of course. We can still do BigUint::trailing_ones easily, but we'd have to take care with BigInt.

[BartMassey]

I think leaving BigInt out for now is probably the path of least resistance. Given that BigInt is sign-magnitude the users can do what they want after the essentially-free conversion to BigUint.

Should count_ones() return u64 or usize? I could make the case either way: neither is ideal. We could make it return BigUint but that seems needlessly silly for most applications…

I'll try to get a PR together. Thanks much!

[BartMassey]

I feel like leading_ones() is not all that useful the way I have implemented it. What is really wanted, I think, is the number of significant_bits() — that is, 1 + position of leftmost 1-bit in the BigUInt. That's what's needed for things like log2(). I can't think of any relevant leading_zeros() measure for BigUInt.

[BartMassey]

Any simple implementation of BigUint::trailing_ones() requires Rust 1.46 or later, but this library is required to compile with Rust 1.31. I stuck trailing_ones() behind an off-by-default feature; advice on how to proceed appreciated.

The obvious plan is to depend on dtolnay's rustversion crate, but I'm not adding that dependency without some discussion from the team.

[cuviper]

I gave a comment on the PR about trailing_ones, which I think we can simply avoid, but generally I use my own autocfg crate in the build script, probing for features rather than hard-coding versions.

[BartMassey]

Sounds good, thanks.

[BartMassey]

Thanks for merging #175 !