Parse an array of bits (`BitArray`) to an integer

Something like this:

function bitarray_to_vector_of_bits(a)
    len = size(a, 1)
    return [SBitVector{len}(sum(i -> UInt(col[i]) << (i-1), 1:len)) for col in eachcol(a)]
end

I see. So do you know why do I get numbers that are different from a straight forward calculation?

The code is assuming that each column has 64 elements, and it’s reinterpreting to Int64 which can take both negative and positive values.

If you want a different type of integer, use e.g. UInt64. Fixing the number of elements per column is harder.

Here is a fast version with zero allocations. You can also control the output through the optional argument s. If the array has more than 63 elements, you can set s = 0.0 or s = big(0) to avoid Int overflow.

function bitarr_to_int5(arr,s=0)
    v = 1
    for i in view(arr,length(arr):-1:1)
        s += v*i
        v <<= 1
    end 
    s
end

arr = BitArray(rand(0:1,50))
@btime bitarr_to_int($arr)
@btime bitarr_to_int2($arr)

  391.547 ns (2 allocations: 992 bytes)
  51.622 ns (0 allocations: 0 bytes)
3 Likes

Sorry for the necrobump, but i might have found another version that is a little bit faster that the accepted solution and thought of leaving this here for future lurkers :smiley: (maybe this is due to some change in julia itself, not sure)

function bitarr_to_int(arr, val = 0)
    v = 2^(length(arr)-1)
    for i in eachindex(arr)
        val += v*arr[i]
        v >>= 1
    end
    return val
end

function bitarr_to_int2(arr, val = 0)
    v = 1
    for i in view(arr, length(arr):-1:1)
        val += v*i
        v <<= 1
    end
    return val
end

b = BitArray(rand(0:1, 50))
@btime bitarr_to_int($b)
@btime bitarr_to_int2($b)

  69.902 ns (0 allocations: 0 bytes)
  91.101 ns (0 allocations: 0 bytes)
5 Likes

I actually just faced this problem in one of my libraries of converting between Integers & BitArrays as fast as possible. Unfortunately I do this conversion a lot so its definitely a hotspot! Here is my solution, though it seems to be slower then the accepted solution for small values (num_bits <= 64) when converting to/from BigInts. I built this to specifically handle very very large numbers of bits. Let me know if you see any improvements I could do to it!

Note: I do not think this will work on a 32 bit processor because BitArray has a UInt64 limb type rather then UInt.

const FastIntConversionType = Union{Base.BitSignedSmall, Base.BitUnsignedSmall, UInt64, Int64}

Base.convert(::Type{BitArray}, i::T) where T <: FastIntConversionType = convert(BitArray, reinterpret(UInt, Int(i)))

function Base.convert(::Type{BitArray}, i::UInt)
    bits = BitArray(undef, sizeof(UInt))
    bits.chunks[1] = reinterpret(UInt, i)
    return bits
end

function Base.convert(::Type{BitArray}, i::BigInt)
    GC.@preserve i begin
        bits = BitArray(undef, i.alloc * sizeof(UInt64))
        unsafe_copyto!(pointer(bits.chunks), i.d, length(bits.chunks))
        return bits
    end
end

function Base.convert(::Type{BigInt}, v::BitArray) 
    GC.@preserve v begin
        num = BigInt(; nbits = Int(8 * ceil(length(v) / 8)))
        limbs = num.alloc
        ptr = Base.GMP.MPZ.limbs_write!(num, limbs)
        unsafe_copyto!(ptr, pointer(v.chunks), length(v.chunks))
        Base.GMP.MPZ.limbs_finish!(num, -limbs)
        return num
    end
end

Base.convert(::Type{Integer}, i::BitArray) = length(i) > 8 * sizeof(Int) ? convert(BigInt, i) : convert(Int, i) 
Base.convert(::Type{T}, i::BitArray) where T <: FastIntConversionType = reinterpret(T, i.chunks[1])
2 Likes

arr = BitArray([1,0,1,0])
What happened to Int64.(arr)?