1const std = @import("../std.zig");
2const builtin = @import("builtin");
3const math = std.math;
4const expect = std.testing.expect;
5
6/// Returns the base-2 logarithm of x.
7///
8/// Special Cases:
9/// - log2(+inf) = +inf
10/// - log2(0) = -inf
11/// - log2(x) = nan if x < 0
12/// - log2(nan) = nan
13pub fn log2(x: anytype) @TypeOf(x) {
14 const T = @TypeOf(x);
15 return switch (@typeInfo(T)) {
16 .comptime_float, .float => @log2(x),
17 .comptime_int => comptime {
18 std.debug.assert(x > 0);
19 var x_shifted = x;
20 // First, calculate floorPowerOfTwo(x)
21 var shift_amt = 1;
22 while (x_shifted >> (shift_amt << 1) != 0) shift_amt <<= 1;
23
24 // Answer is in the range [shift_amt, 2 * shift_amt - 1]
25 // We can find it in O(log(N)) using binary search.
26 var result = 0;
27 while (shift_amt != 0) : (shift_amt >>= 1) {
28 if (x_shifted >> shift_amt != 0) {
29 x_shifted >>= shift_amt;
30 result += shift_amt;
31 }
32 }
33 return result;
34 },
35 .int => |int_info| math.log2_int(switch (int_info.signedness) {
36 .signed => @Int(.unsigned, int_info.bits -| 1),
37 .unsigned => T,
38 }, @intCast(x)),
39 else => @compileError("log2 not implemented for " ++ @typeName(T)),
40 };
41}
42
43test log2 {
44 // https://github.com/ziglang/zig/issues/13703
45 if (builtin.cpu.arch == .aarch64 and builtin.os.tag == .windows) return error.SkipZigTest;
46
47 try expect(log2(@as(f32, 0.2)) == @log2(0.2));
48 try expect(log2(@as(f64, 0.2)) == @log2(0.2));
49 comptime {
50 try expect(log2(1) == 0);
51 try expect(log2(15) == 3);
52 try expect(log2(16) == 4);
53 try expect(log2(1 << 4073) == 4073);
54 }
55}