Open
Description
The method for Base.top_set_bit for general integers may give incorrect results:
julia> using Base: top_set_bit
julia> top_set_bit(2^50)
51
julia> invoke(top_set_bit, Tuple{Integer}, 2^50)
50
The reason is that inside
Line 706 in b18d2cc
the added
1 may get lost due to the limited floating-point precision used by log2.
All integer types from Base except for Bool have dedicated methods for top_set_bit,
julia> methods(top_set_bit)
# 3 methods for generic function "top_set_bit" from Base:
[1] top_set_bit(x::BigInt)
@ Base.GMP gmp.jl:608
[2] top_set_bit(x::Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8})
@ int.jl:509
[3] top_set_bit(x::Integer)
@ intfuncs.jl:668
so I don't know if this generic method is supposed to be relevant at all (beyond Bool). I stumbled upon this bug when using top_set_bit for large integers defined by BitIntegers.jl.
The function top_set_bit was introduced in #47523. This comment sounds as if the function is not meant to be public. On the other hand, it does have a docstring. Since top_set_bit appears to be faster than ndigits,
julia> x = Int64(2)^60; @btime top_set_bit($x); @btime ndigits($x; base = 2, pad = 0);
3.001 ns (0 allocations: 0 bytes)
6.088 ns (0 allocations: 0 bytes)
julia> x = Int128(2)^120; @btime top_set_bit($x); @btime ndigits($x; base = 2, pad = 0);
2.672 ns (0 allocations: 0 bytes)
8.461 ns (0 allocations: 0 bytes)
it would be a pity if it were not considered public.
I used Julia 1.10.0. The problem is still present in master.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment