Covert BitArray to Int64

General Usage
1

Hi,

Is there a simple (and efficient) method to convert a BitArray to an Int64, treating the BitArray as the binary representation an Int64?

Thanks!

2 
xbitmap = Int64(2) .^ collect(63:-1:0);

testval = bits(2323232);
bitvec = map(x->x=='1', collect(testval)); #equiv# collect(testval).=='1';
sum(xbitmap[bitvec]) == 2323232
3

If b is a 64-element BitArray, then b.chunks[1] is the same data as an Int64, but in bit-reversed order. There are various algorithms for efficiently bit-reversing back to regular order; I’m not sure which one is the fastest, but you can definitely do better than going bit-by-bit.

(But if this conversion is really performance-critical for you then a BitArray may not be the best choice of data structure.)

3 Likes
4 
function revbits(z::UInt64)
           z = (((z & 0xaaaaaaaaaaaaaaaa) >>  1) | ((z & 0x5555555555555555) <<  1))
           z = (((z & 0xcccccccccccccccc) >>  2) | ((z & 0x3333333333333333) <<  2))
           z = (((z & 0xf0f0f0f0f0f0f0f0) >>  4) | ((z & 0x0f0f0f0f0f0f0f0f) <<  4))
           z = (((z & 0xff00ff00ff00ff00) >>  8) | ((z & 0x00ff00ff00ff00ff) <<  8))
           z = (((z & 0xffff0000ffff0000) >> 16) | ((z & 0x0000ffff0000ffff) << 16))
           z = (((z & 0xffffffff00000000) >> 32) | ((z & 0x00000000ffffffff) << 32))
           return z
       end

not the fastest (table lookups are) but handy

1 Like
5

It might be even easier to just build your own array type that just uses the Int directly as its storage:

julia> mutable struct IntBitVec <: AbstractVector{Bool}
           data::UInt64
       end
       Base.size(::IntBitVec) = (64,)
       @inline function Base.getindex(v::IntBitVec, i::Int)
           @boundscheck checkbounds(v, i)
           v.data & (1 << (i-1)) != 0 # Just change i-1 to 65-i to reverse the bits
       end

julia> IntBitVec(1)
64-element IntBitVec:
  true
 false
 false
 false
     ⋮

julia> IntBitVec(2)
64-element IntBitVec:
 false
  true
 false
 false
     ⋮
1 Like
6

A somewhat low effort solution is to punt the problem to llvm:

@inline bitreverse(x::UInt64)=
          Base.llvmcall(("declare i64 @llvm.bitreverse.i64(i64)",
        "%retval = call i64 @llvm.bitreverse.i64(i64 %0)
        ret i64 %retval"), UInt64, Tuple{UInt64}, x)

This gives beautiful @code_llvm; but JeffreySarnoff’s variant is surprisingly much better than the llvm intrinsic:

using BenchmarkTools
zz=rand(UInt64)
@btime bitreverse($zz)
#30.144 ns (0 allocations: 0 bytes)
@btime revbits($zz)
#  8.298 ns (0 allocations: 0 bytes)

Props; I would not have expected to do better than the authors of llvm implementing an intrinsic, especially if you compile through llvm!

2 Likes
7

Here’s another attempt using matrix multiply

ba = BitArray(rand(20, 64) .> 0.5);
@time ba * xbitmap 
> 0.000013 sec (5 alloc, 400 bytes)

ba = BitArray(rand(200000, 64) .> 0.5);
@time ba * xbitmap 
> 0.068 sec (6 alloc, 1.52MiB bytes)

at 20,000,000 x 64 it takes 10.x sec (/9.6 GiB) to generate the bitarray and 8.x sec(/150MiB) to convert back to Int64’s