Skip to content

generic method for top_set_bit gives wrong result #53887

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

top_set_bit(x::Integer) = ceil(Integer, log2(x + oneunit(x)))

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

Metadata

Assignees

No one assigned

    Labels

    mathsMathematical functions

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions