13 ms·

What is the correct implementation of this?

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 ago
  This gives you the number of set bits, not the next larger number with the same number of set bits.
  - psychphysic 4y ago
    Filter 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 ago
      Step 1 is computing a set of ~2^64 things?
      - psychphysic 4y ago
        Lol 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 ago
        You 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.
anonymoushn 4y ago
I think something like this would handle it const std = @import("std"); fn snoob(x_: anytype) @TypeOf(x_) { const T = @TypeOf(x_); const U = comptime std.meta.Int(.unsigned, std.meta.bitCount(T)); const x = @bitCast(U, x_); const tz = @ctz(x); const pc = @popCount(x); const L2U = comptime std.meta.Int(.unsigned, std.meta.bitCount(@TypeOf(tz))-1); if (tz + pc == std.meta.bitCount(T)) { if (pc == 0) { return 0; } return @bitCast(T, (x >> @intCast(L2U, tz))); } const smallest = @as(U, 1) << @intCast(L2U, tz); const ripple = x + smallest; const ones = ((x ^ ripple) >> 2) >> @intCast(L2U, tz); return ripple | ones; } pub fn main() void { std.debug.print("Hello, {d}!", .{snoob(@as(u32,5))}); } In addition to the stated problems with wraparound and zero (claimed fixed here) the implementation in this header file seems to have some potential correctness issue if you pass in a signed type and end up performing right shifts on values with the sign bit set and your compiler decides this means you want sign extension. Edit: translation back to C++ using other functions in this header and assuming that a bt_unsigned exists which is similar to the already included bt_signed: template <typename T> inline T GetNextWithEqualBitCount(T x_) { bt_unsigned x, smallest, ripple, ones; int tz, pc; x = (bt_unsigned)x_; tz = CountTrailing0Bits(x); pc = CountBits(x); if (tz + pc == sizeof(x)*8) { if (pc == 0) { return 0; } return (T)(x >> tz); } smallest = ((bt_unsigned)1) << tz; ripple = x + smallest; ones = ((x ^ ripple) >> 2) >> tz; return (T)(ripple | ones); } runnable demo: https://www.sololearn.com/compiler-playground/c6iz3kHpZ3zP https://www.sololearn.com/compiler-playground/c6iz3kHpZ3zP
- anonymoushn 4y ago
  The 2nd branch here only exists because shifting a uint32_t right by 32 is undefined. You can avoid it if you do 2 shifts instead. The first branch is tougher to get rid of.

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 ago
This gives you the number of set bits, not the next larger number with the same number of set bits.
- psychphysic 4y ago
  Filter 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 ago
    Step 1 is computing a set of ~2^64 things?
    - psychphysic 4y ago
      Lol 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 ago
      You 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.

anonymoushn 4y ago

I think something like this would handle it const std = @import("std"); fn snoob(x_: anytype) @TypeOf(x_) { const T = @TypeOf(x_); const U = comptime std.meta.Int(.unsigned, std.meta.bitCount(T)); const x = @bitCast(U, x_); const tz = @ctz(x); const pc = @popCount(x); const L2U = comptime std.meta.Int(.unsigned, std.meta.bitCount(@TypeOf(tz))-1); if (tz + pc == std.meta.bitCount(T)) { if (pc == 0) { return 0; } return @bitCast(T, (x >> @intCast(L2U, tz))); } const smallest = @as(U, 1) << @intCast(L2U, tz); const ripple = x + smallest; const ones = ((x ^ ripple) >> 2) >> @intCast(L2U, tz); return ripple | ones; } pub fn main() void { std.debug.print("Hello, {d}!", .{snoob(@as(u32,5))}); } In addition to the stated problems with wraparound and zero (claimed fixed here) the implementation in this header file seems to have some potential correctness issue if you pass in a signed type and end up performing right shifts on values with the sign bit set and your compiler decides this means you want sign extension. Edit: translation back to C++ using other functions in this header and assuming that a bt_unsigned exists which is similar to the already included bt_signed: template <typename T> inline T GetNextWithEqualBitCount(T x_) { bt_unsigned x, smallest, ripple, ones; int tz, pc; x = (bt_unsigned)x_; tz = CountTrailing0Bits(x); pc = CountBits(x); if (tz + pc == sizeof(x)*8) { if (pc == 0) { return 0; } return (T)(x >> tz); } smallest = ((bt_unsigned)1) << tz; ripple = x + smallest; ones = ((x ^ ripple) >> 2) >> tz; return (T)(ripple | ones); } runnable demo: https://www.sololearn.com/compiler-playground/c6iz3kHpZ3zP https://www.sololearn.com/compiler-playground/c6iz3kHpZ3zP

anonymoushn 4y ago
The 2nd branch here only exists because shifting a uint32_t right by 32 is undefined. You can avoid it if you do 2 shifts instead. The first branch is tougher to get rid of.