2 ms·
I think something like this would handle it const std = @import("std"); fn snoob(x_: anytype) @TypeOf(x_) { const T = @TypeOf(x_); const U = com
by 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 agoThe 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.