Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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


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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: