log2

pub fn log2(x: anytype) @TypeOf(x)

File

Code

pub fn log2(x: anytype) @TypeOf(x) {
    const T = @TypeOf(x);
    return switch (@typeInfo(T)) {
        .comptime_float, .float => @log2(x),
        .comptime_int => comptime {
            std.debug.assert(x > 0);
            var x_shifted = x;
            // First, calculate floorPowerOfTwo(x)
            var shift_amt = 1;
            while (x_shifted >> (shift_amt << 1) != 0) shift_amt <<= 1;

            // Answer is in the range [shift_amt, 2 * shift_amt - 1]
            // We can find it in O(log(N)) using binary search.
            var result = 0;
            while (shift_amt != 0) : (shift_amt >>= 1) {
                if (x_shifted >> shift_amt != 0) {
                    x_shifted >>= shift_amt;
                    result += shift_amt;
                }
            }
            return result;
        },
        .int => |int_info| math.log2_int(switch (int_info.signedness) {
            .signed => @Int(.unsigned, int_info.bits -| 1),
            .unsigned => T,
        }, @intCast(x)),
        else => @compileError("log2 not implemented for " ++ @typeName(T)),
    };
}