Don't understand how nextpow works

user_15165527 0
Viewed 53

Recently I have been looking at how the nextpow(a::Real, x::Real) function works inside. The code is in base/intfuncs.jl of the Julia project. For the case a == 2 there is an optimization as it is very common as case.

a == 2 && isa(x, Integer) && return _nextpow2(x)

However, I don't understand how this case works, I understand that this manipulation of bits must be something common to find the next a^n, but right now I don't understand it.

_nextpow2(x::Unsigned) = oneunit(x)<<((sizeof(x)<<3)-leading_zeros(x-oneunit(x)))
_nextpow2(x::Integer) = reinterpret(typeof(x),x < 0 ? -_nextpow2(unsigned(-x)) : _nextpow2(unsigned(x)))

In particular what I don't understand is the function _nextpow2(x::Unsigned). Why does this help to get a^n larger than x?

julia pow
1 Answers

for an unsigned Int, whatever its bitstring() is, say 0000000001xxxxxx, the next power of 2 is just put a 1 at the last leading 0 and replace the entire 1xxxxxx with 0000000

julia> function f(x)
           @show bitstring(x)
           oneU = oneunit(x)
           Nbits = sizeof(x)<<3 # Nbits = Nbytes * 8
           Nzeros = leading_zeros(x - oneU)
           @show oneU
           @show Nbits
           @show Nzeros
           res = oneU <<(Nbits-Nzeros)
           @show bitstring(res)
           res
       end


julia> f(UInt16(18))
bitstring(x) = "0000000000010010"
oneU = 0x0001
Nbits = 16
Nzeros = 11
bitstring(res) = "0000000000100000"
0x0020
user_29606950
Related