integer bit ops

more_bitops.jl

# some more bit related operators for Julia
# Jeffrey Sarnoff (2012-Oct-07)

# bitsizeof, allbits1, lsbs1, lsbs0, msbs1, msbs0,
# rol, ror, ispow2, pow2lte, pow2gte, pow2lt, pow2gt,  
# signs_differ, signs_same, floor_avg, ceil_avg

bitsizeof(x) = sizeof(x)<<3

SUS = Union{Signed,Unsigned}

# unsigned <--> signed for types as well as values
for (U,I) in [(:UInt8, :Int8), (:UInt16, :Int16), (:UInt32, :Int32),
              (:UInt64, :Int64), (:UInt128, :Int128)]
    @eval begin
        unsigned(::Type{($I)}) = ($U)
        signed(::Type{($U)})   = ($I)
    end
end

# all bits set to 1 (use zero(Type) to get all bits 0) 
for T in [:UInt8, :UInt16, :UInt32, :UInt64, :UInt128]
    @eval allbits1(::Type{($T)}) where {T} = typemax(($T))
end
for T in [:Int8, :Int16, :Int32, :Int64, :Int128]
    @eval allbits1(::Type{($T)}) where {T} = reinterpret(($T),typemax(unsigned($T)))
end
allbits1(x::T) where {T<:SUS}= allbits1(T)


# lsbs0(n) == 1...10..0 (n 0b)   lsbs1(n) == 0...01..1 (n 1b)
# msbs0(n) == 0..01...1 (n 0b)   msbs1(n) == 1..10...0 (n 1b)
# lsbs_(T,n) == lsbs_(n::T)      msbs_(T,n) == msbs_(n::T)

lsbs0(n::T) where {T<:Unsigned} =  (allbits1(T) << n)
lsbs1(n::T) where {T<:Unsigned} = ~(allbits1(T) << n)
msbs0(n::T) where {T<:Unsigned} =  lsbs1(bitsizeof(T)-n)
msbs1(n::T) where {T<:Unsigned} = ~(lsbs1(bitsizeof(T)-n))

lsbs0(::Type{T}, n::Int) where {T<:Unsigned}= lsbs0(convert(T,n))
lsbs1(::Type{T}, n::Int) where {T<:Unsigned}= lsbs1(convert(T,n))
msbs0(::Type{T}, n::Int) where {T<:Unsigned}= msbs0(convert(T,n))
msbs1(::Type{T}, n::Int) where {T<:Unsigned}= msbs1(convert(T,n))

lsbs0(n::T) where {T<:Signed} = convert(Signed,lsbs0(convert(Unsigned,n)))
lsbs1(n::T) where {T<:Signed} = convert(Signed,lsbs1(convert(Unsigned,n)))
msbs0(n::T) where {T<:Signed} = convert(Signed,msbs0(convert(Unsigned,n)))
msbs1(n::T) where {T<:Signed} = convert(Signed,msbs1(convert(Unsigned,n)))

lsbs0(::Type{T}, n::Int) where {T<:Signed}  = lsbs0(convert(T,n))
lsbs1(::Type{T}, n::Int) where {T<:Signed}  = lsbs1(convert(T,n))
msbs0(::Type{T}, n::Int) where {T<:Signed}  = msbs0(convert(T,n))
msbs1(::Type{T}, n::Int) where {T<:Signed}  = msbs1(convert(T,n))


# x <= 0 cannot be an integer power of 2
ispow2(x::Unsigned) = ((x == 0) == (x & (x-1)))
ispow2(x::Signed  ) = ((x <= 0) == (x & (x-1)))

# the largest power of 2 <= x
_pow2lte(x::SUS) = one(x) << (bitsizeof(x)-(leading_zeros(x)+1))
pow2lte(x::SUS)  = ( (x > 0) ? _pow2lte(x) :  
                               error("pow2lte($(x)) undefined") )
# the smallest power of 2 >= x
_pow2gte(x::Unsigned) = one(x) << (bitsizeof(x)-(leading_zeros(x-1)))
pow2gte(x::Unsigned)  = ( (x >= 0) ? _pow2gte(x) :  
                                error("pow2gte($(x)) undefined") )
_pow2gte(x::T) where {T<:Signed} = one(x) << (bitsizeof(x)-(leading_zeros(x-1)))
pow2gte(x::T) where {T<:Signed} = ( (0 <= x <= (typemax(T)>>1)) ? _pow2gte(x) :
                                error("pow2gte($(x)) undefined") )

# the largest power of 2 < x
pow2lt(x::SUS) = ( (x > 1) ? _pow2lte(x-1) :  
                             error("pow2gt($(x)) undefined") )
# the smallest power of 2 > x
pow2gt(x::Unsigned) = ( (x >= 0) ? pow2gte(x+1) :  
                              error("pow2gt($(x)) undefined") )
pow2gt(x::T) where {T<:Signed} = ( (x >= 0) ? pow2gte(x+1) :  
                              error("pow2gt($(x)) undefined") )




# signs_differ, signs_same
# this algorithm is credited to Manfred Weis (2009) and given at
# http://graphics.stanford.edu/~seander/bithacks.html#DetectOppositeSigns
#

for T in (:UInt8, :UInt16, :UInt32, :UInt64, :UInt128)
    @eval begin
        signs_differ(h::($T), k::($T)) = false
        signs_same(h::($T), k::($T)) = true
    end
end

for T in (:Int8, :Int16, :Int32, :Int64, :Int128)
    @eval begin
        signs_differ(h::($T), k::($T)) = ((h $ k) <  zero(($T)))
        signs_same(h::($T), k::($T)) = ((h $ k) >= zero(($T)))
    end
end

# average of two values
# this algorithm is from Henry G. Dietz's site http://aggregate.org/MAGIC
# elaborated by Henry S. Warren, Jr. in Hacker's Delight 2nd ed p19

floor_avg(a::T, b::T) where {T<:Unsigned} = ( (a & b) + ((a $ b)>>>1) )
floor_avg(a::T, b::T) where {T<:Signed}   = ( (a & b) + ((a $ b)>>1)  )
ceil_avg(a::T, b::T)  where {T<:Unsigned} = ( (a | b) - ((a $ b)>>>1) )
ceil_avg(a::T, b::T)  where {T<:Signed}   = ( (a | b) - ((a $ b)>>1)  )