3 ms·
Have a look at popcount[0]. It's even a single instruction on many platforms [1]. [0] https://en.cppreference.com/w/cpp/numeric/popcount https://en.cppreferenc
by psychphysic 4y ago
Have a look at popcount[0]. It's even a single instruction on many platforms [1].
[0] https://en.cppreference.com/w/cpp/numeric/popcount https://en.cppreference.com/w/cpp/numeric/popcount
[1] https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/
- danbruc 4y agoThis gives you the number of set bits, not the next larger number with the same number of set bits.
- psychphysic 4y agoFilter larger, zip Popcount, filter with same popcount, min. If you need the full implementation spelled out I can do that when I get in from my commute home.
- anonymoushn 4y agoStep 1 is computing a set of ~2^64 things?
- psychphysic 4y agoLol just gotten in and looked at this at a desktop I thought we were filtering a list. My bad. Funny though. Interesting task I guess really you want to find the first (from right) and move the first set bit left to fill it.
- danbruc 4y agoYou could keep incrementing from the current value until the population count matches again, but in the worst case - probably from 2^62 to 2^63 with a single set bit or wrapping around from 2^63 to 2^0 - that would still take pretty much 2^64 steps.