不明白下一个pow是如何工作的

Question

最近我一直在研究nextpow(a::Real, x::Real)函数是如何在内部工作的。代码在Julia项目的base/intfuncs.jl中。对于a == 2的情况，有一个优化，因为它是非常常见的情况。

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

然而，我不明白这种情况是如何工作的，我明白这种位的操纵必须是找到下一个a^n的共同之处，但是现在我不明白它。

_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)))

我特别不理解的是_nextpow2(x::Unsigned)函数。为什么这有助于使a^n大于x?

Answer 1

对于无符号整型，不管bitstring()是什么，比如0000000001xxxxxx，下一个2的幂就是在最后一个前导0上放一个1，然后用0000000替换整个1xxxxxx

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