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

**URL:** <https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361>\
**Category:** New to Julia\
**Tags:** question\
**Created:** [July 1, 2020, 11:41am UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361 "2020-07-01T11:41:45Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![roi.holtzman](https://avatars.discourse-cdn.com/v4/letter/r/f05b48/32.png) [@roi.holtzman](https://discourse.julialang.org/u/roi.holtzman)\
**Post date:** [July 1, 2020, 11:41am UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/1 "2020-07-01T11:41:45Z")

</div>

I want to parse an array of bits to a decimal number.  
I am using this function now but it does not work very fast

```julia
function bitarr_to_int(arr)
    return sum(arr .* (2 .^ collect(length(arr)-1:-1:0)))
end

```

Is there a way to perform this conversion fast?  
I tried to use `parse` but it only get strings, and I couldn’t convert the `BitArray` to a string properly.

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [July 1, 2020, 12:17pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/2 "2020-07-01T12:17:50Z")

</div>

You could access the underlying `UInt` array directly with `arr.chunks`. Does the following work for you?

```julia
sum(((i, x),) -> big(x) << ((i-1) * 8sizeof(x)), enumerate(arr.chunks))

```

I think your solution currently works the opposite way, so you might have to do `reverse(arr)` first.

---

<div class="post-metadata">

**Author:** ![roi.holtzman](https://avatars.discourse-cdn.com/v4/letter/r/f05b48/32.png) [@roi.holtzman](https://discourse.julialang.org/u/roi.holtzman)\
**Post date:** [July 1, 2020, 12:33pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/3 "2020-07-01T12:33:27Z")

</div>

It does work, but it seems slower than the original function I posted.  
Is there something I am doing wrong?

```julia
julia> function bitarr_to_int(arr)
           return sum(arr .* (2 .^ collect(length(arr)-1:-1:0)))
       end
bitarr_to_int (generic function with 1 method)

julia> function bittest(arr)
           arr = reverse(arr)
           sum(((i, x),) -> big(x) << ((i-1) * sizeof(x)), enumerate(arr.chunks))
       end
bittest (generic function with 1 method)

julia> arr = BitArray([1,0,1,0])
4-element BitArray{1}:
 1
 0
 1
 0

julia> @time bitarr_to_int(arr)
  0.153301 seconds (520.49 k allocations: 25.100 MiB)
10

julia> @time bitarr_to_int(arr)
  0.000005 seconds (6 allocations: 384 bytes)
10

julia> @time bittest(arr)
  0.096877 seconds (218.42 k allocations: 11.088 MiB)
10

julia> @time bittest(arr)
  0.000021 seconds (13 allocations: 440 bytes)
10

```

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [July 1, 2020, 12:39pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/4 "2020-07-01T12:39:02Z")

</div>

Your original function uses `BigInt`? It seems to me that it just works over `Int`s. The `bittest` functions explicitly converts to `BigInt`s. You were sure the original `BitArray` had not more than 63~64 elements?

---

<div class="post-metadata">

**Author:** ![roi.holtzman](https://avatars.discourse-cdn.com/v4/letter/r/f05b48/32.png) [@roi.holtzman](https://discourse.julialang.org/u/roi.holtzman)\
**Post date:** [July 1, 2020, 12:45pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/5 "2020-07-01T12:45:25Z")

</div>

You are right.  
This function gives a bit better performance:

```julia
julia> function bittest2(arr)
           arr = reverse(arr)
           sum(((i, x),) -> Int(x) << ((i-1) * sizeof(x)), enumerate(arr.chunks))
       end
bittest2 (generic function with 1 method)

julia> @time bittest2(arr)
  0.090779 seconds (68.21 k allocations: 3.137 MiB)
10

julia> @time bittest2(arr)
  0.000004 seconds (7 allocations: 304 bytes)
10

```

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [July 1, 2020, 12:47pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/6 "2020-07-01T12:47:23Z")

</div>

If your array never contains more than 64 entries, you can just use `arr.chunks[1]`. I chose `BigInt` here, because your example overflows if there are more than 63 entries in `arr`.

---

<div class="post-metadata">

**Author:** ![roi.holtzman](https://avatars.discourse-cdn.com/v4/letter/r/f05b48/32.png) [@roi.holtzman](https://discourse.julialang.org/u/roi.holtzman)\
**Post date:** [July 1, 2020, 12:55pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/7 "2020-07-01T12:55:04Z")

</div>

I see. I know that my arrays are always \< 60 entries, so I do not need the `BigInt`.

I want to run this conversion for 10^7 such arrays.  
When I run both functions in a for loop, they give roughly the same result (your method is ~7 seconds, and my original function is ~11 seconds).  
Is there a better way to run this for an entire 2d array (in the appropriate axis of course)?

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [July 1, 2020, 1:03pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/8 "2020-07-01T13:03:50Z")

</div>

`arr.chunks[1]` should basically be free. `reverse` might be expensive. The inplace `reverse!` might be a bit more efficient here, because it shouldn’t allocate. A better solution might be to restructure your code a bit, so you don’t need to reverse the array. It’s difficult to give concrete tips without knowing a bit more about your application. Are you currently using a 2d BitArray? If so, it might be a better solution to use a `Vector{UInt}` as your data structure and implement the bit-twiddling yourself.

---

<div class="post-metadata">

**Author:** ![roi.holtzman](https://avatars.discourse-cdn.com/v4/letter/r/f05b48/32.png) [@roi.holtzman](https://discourse.julialang.org/u/roi.holtzman)\
**Post date:** [July 1, 2020, 1:20pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/9 "2020-07-01T13:20:08Z")

</div>

Thanks for the answer.  
I have a 2d array of bits. Each row is the bit array I am willing to convert to an `int`.  
I guess I thought that even for 10^7 rows in such a 2d `BitArray`, the operation should be quite fast - my intuition was wrong.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [July 1, 2020, 1:31pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/10 "2020-07-01T13:31:47Z")

</div>

It _should_ be fast, if you can use `.chunks` and `reinterpret`, but you should be working along columns, not rows for good performance. Also, if each row/column has _less_ than 60 elements, how do you wish to interpret the missing bits needed to make up a 64 bit integer?

```julia
julia> R = bitrand(64, 10^7); # working along the columns, not rows

julia> @btime reinterpret(Int64, ($R).chunks);
  8.264 ns (1 allocation: 32 bytes) # fast enough?

```

With less than 64 elements you need to apply some bitmask or something.

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [July 1, 2020, 1:37pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/11 "2020-07-01T13:37:15Z")

</div>

If you decide to go with a vector of UInts, here is how you can treat a single UInt like a BitVector:

```julia
julia> struct SBitVector <: AbstractVector{Bool}
           x::UInt
           len::Int
       end

julia> Base.size(v::SBitVector) = (v.len,)

julia> Base.@propagate_inbounds function Base.getindex(v::SBitVector, i::Int)
           Base.@boundscheck 1 <= i <= length(v)
           return (v.x >> (i-1)) % Bool
       end

julia> Base.@propagate_inbounds function Base.setindex(v::SBitVector, i::Int, x::Bool)
           Base.@boundscheck 1 <= i <= length(v) || throw(BoundsError(v, i))
           mask = UInt(1) << (i-1)
           res = ifelse(x, v.x | mask, v.x & ~mask)
           return SBitVector(res, v.len)
       end

julia> v = SBitVector(rand(UInt8), 8)
8-element SBitVector:
 0
 1
 1
 0
 1
 0
 0
 0

julia> v[3]
true

julia> Base.setindex(v, 3, false)
8-element SBitVector:
 0
 1
 0
 0
 1
 0
 0
 0

```

You could then just make a vector of `SBitVector`s.

Edit:  
Probably more efficient in most cases, if the length is a type parameter:

```julia
julia> struct SBitVector{len} <: AbstractVector{Bool}
           x::UInt
       end

julia> Base.size(v::SBitVector{len}) where {len} = (len,)

julia> Base.@propagate_inbounds function Base.getindex(v::SBitVector, i::Int)
           Base.@boundscheck 1 <= i <= length(v) || throw(BoundsError(v, i))
           return (v.x >> (i-1)) % Bool
       end

julia> Base.@propagate_inbounds function Base.setindex(v::SBitVector{len}, i::Int, x::Bool) where {len}
           Base.@boundscheck 1 <= i <= length(v) || throw(BoundsError(v, i))
           mask = UInt(1) << (i-1)
           res = ifelse(x, v.x | mask, v.x & ~mask)
           return SBitVector{len}(res)
       end

julia> v = SBitVector{8}(rand(UInt8))
8-element SBitVector{8}:
 0
 1
 1
 1
 0
 0
 1
 1

julia> v[3]
true

julia> Base.setindex(v, 3, false)
8-element SBitVector{8}:
 0
 1
 0
 1
 0
 0
 1
 1

```

---

<div class="post-metadata">

**Author:** ![roi.holtzman](https://avatars.discourse-cdn.com/v4/letter/r/f05b48/32.png) [@roi.holtzman](https://discourse.julialang.org/u/roi.holtzman)\
**Post date:** [July 1, 2020, 1:43pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/12 "2020-07-01T13:43:31Z")

</div>

I am actually working with columns (I wrote rows, because I thought it is more natural for understanding).

Each column has 20 rows - so it is a 20 bit number. I would like to read it as a 20 bit number - like padding all of first 44 bits with zeros.

I tried to run the `reinterpret` function you used. I do not understand the `$` sign before the `R`. It does not run like this for me.  
I ran `reinterpret(Int64, (R).chunks)` , but as a result I get also negative numbers, which should not be. So I do not really understand how this works.

Could you explain a bit more on how to use `reinterpret` here?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [July 1, 2020, 1:49pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/13 "2020-07-01T13:49:38Z")

</div>

> [@roi.holtzman](#):
>
> Each column has 20 rows - so it is a 20 bit number. I would like to read it as a 20 bit number - like padding all of first 44 bits with zeros.

I am not sure I understand the context, but if possible, I would just consider building an `UInt64` directly with `|` and `1 << index` when processing the original data.

---

<div class="post-metadata">

**Author:** ![roi.holtzman](https://avatars.discourse-cdn.com/v4/letter/r/f05b48/32.png) [@roi.holtzman](https://discourse.julialang.org/u/roi.holtzman)\
**Post date:** [July 1, 2020, 2:07pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/14 "2020-07-01T14:07:45Z")

</div>

> [@Tamas\_Papp](#):
>
> I am not sure I understand the context, but if possible, I would just consider building an `UInt64` directly with `|` and `1 << index` when processing the original data.

I think that you mean that you would not maintain the bit array, but just get the integer number?  
I need the entire bit array, because I want to drop some of the bits by hand.

I did not follow on what you meant with `|` and `1<<index`. Could you explain that? Maybe it could still help me somehow.

---

<div class="post-metadata">

**Author:** ![roi.holtzman](https://avatars.discourse-cdn.com/v4/letter/r/f05b48/32.png) [@roi.holtzman](https://discourse.julialang.org/u/roi.holtzman)\
**Post date:** [July 1, 2020, 2:17pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/15 "2020-07-01T14:17:17Z")

</div>

That is nice!  
But I need the other direction: to go from a bit-vector to an int.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [July 1, 2020, 2:18pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/16 "2020-07-01T14:18:22Z")

</div>

Start with

```julia
z = UInt64(0)

```

Whenever you want to set the bit for `index`, do

```julia
z |= 1 << index

```

You can query bits in a similar way. This is basically what `BitArray` does under the hood, but in a much more organized way, allowing longer vectors etc, but if you need the basics it is really simple.

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [July 1, 2020, 2:18pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/17 "2020-07-01T14:18:51Z")

</div>

That’s easy, you can just use `v.x` as above.

---

<div class="post-metadata">

**Author:** ![roi.holtzman](https://avatars.discourse-cdn.com/v4/letter/r/f05b48/32.png) [@roi.holtzman](https://discourse.julialang.org/u/roi.holtzman)\
**Post date:** [July 1, 2020, 2:24pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/18 "2020-07-01T14:24:05Z")

</div>

I see. So how can I construct it using a `BitArray`?

---

<div class="post-metadata">

**Author:** ![roi.holtzman](https://avatars.discourse-cdn.com/v4/letter/r/f05b48/32.png) [@roi.holtzman](https://discourse.julialang.org/u/roi.holtzman)\
**Post date:** [July 1, 2020, 2:33pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/19 "2020-07-01T14:33:33Z")

</div>

Thanks. I tried that, but it gives the same performance as before.

Similar to @simeonschaub suggestions here:

> [@simeonschaub](#):
>
> ```julia
> sum(((i, x),) -> big(x) << ((i-1) * 8sizeof(x)), enumerate(arr.chunks))
> 
> ```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [July 1, 2020, 2:35pm UTC](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361/20 "2020-07-01T14:35:04Z")

</div>

The `$` sign is used for benchmarking, with the BenchmarkTools package.

[Next page](https://discourse.julialang.org/t/parse-an-array-of-bits-bitarray-to-an-integer/42361.md?page=2)