`Vector{Bool}` to Int

General Usage
1

I’m using PyCall to interact with a python package which returns integers as a Vector{Bool}, e.g. [true, true, false, true, true, true, false, true]. How can I easily convert this to an integer?

In a previous question it’s shown how to convert from a bool Str to Int

2

Should be as simple as this:

julia> v = [true, true, false, true, true, true, false, true]
8-element Vector{Bool}:
 1
 1
 0
 1
 1
 1
 0
 1

julia> Int.(v)
8-element Vector{Int64}:
 1
 1
 0
 1
 1
 1
 0
 1
3

Sorry perhaps it wasn’t clear. I’d like to interpret it as

parse(Int, "11011101"; base=2)

So the initial example gives 221

4

It’s a bit esoteric, but this works:

julia> only(BitVector(reverse(v)).chunks) |> Int
221

There may be a better way.

2 Likes
5

Slightly esoteric but it does work, unless someone has a clearer solution I’ll stick with this. Thank you.

6

You can just use the String method in your OP if you construct the string:

julia> parse(Int, join(Int.(v), ""), base = 2)
221

maybe less esoteric, but probably less efficient than the current solution.

1 Like
7

Less esoteric but still fast:

julia> evalpoly(2, reverse(v))
221

More esoteric and faster yet:

julia> mapreduce(((i, v),) -> (v << (i - 1)), |, enumerate(Iterators.reverse(v)))
221
7 Likes
8

I think the evalpoly is the cleanest and not so slow

1 Like
9

By modifying the base function so that you don’t have to reverse v, you gain performance


function _evalpoly(x, p)
    N = length(p)
    ex = p[1]
    for i in 2:N
        ex *= x
        ex+=p[i]
    end
    ex
end
10

In my opinion the cleanest, and 4x faster than the fastest mapreduce solution above,:

reduce((acc, b) -> acc << 1 + b, v; init=0)

Its just 8 bitshifts and 8 additions and is pretty self explanatory, we just shift the Int accumulator left and add the next Bool as the lowest bit

4 Likes
11

really nice, but not the fastest

julia> using BenchmarkTools

julia> function polyeval(x, p)
           N = length(p)
           ex = p[1]
           for i in 2:N
               ex *= x
               ex+=p[i]
           end
           ex
       end
polyeval (generic function with 1 method)

julia> @btime polyeval(2,v)
  16.533 ns (0 allocations: 0 bytes)
221

julia> @btime reduce((x,y)->x<<1+y, v; init=0)
  70.902 ns (0 allocations: 0 bytes)
221

julia> @btime evalpoly(2, reverse(v))
  55.589 ns (1 allocation: 64 bytes)
221

julia> @btime mapreduce(((i, v),) -> (v << (i - 1)), |, enumerate(Iterators.reverse(v)))
  150.181 ns (3 allocations: 48 bytes)
221

julia> @btime only(BitVector(reverse(v)).chunks) |> Int
  316.949 ns (3 allocations: 160 bytes)
221
12

The base for loop performs even better if it specializes in the specific case of base 2 numbers

julia> function poly_2_eval(p)
           ex = 0
           for e in p
               ex *= 2
               ex+=e
           end
           ex
       end
poly_2_eval (generic function with 1 method)

julia> @btime poly_2_eval(v)
  15.030 ns (0 allocations: 0 bytes)
221
13

It’s fun to play the benchmarks game, but let’s step back here and remember the context — this Vector{Bool} is coming from a Python function. Performance of a linear-time conversion is unlikely to matter in this context, so I would just go with any solution that is clear and requires little code, e.g. evalpoly(2, reverse(v)).

4 Likes
14

@rocco_sprmnt21 Its not the fastest because you are not using $ in your benchmarks, so most of the time is in how the type instability is handled, in polyeval it just quickly hits a function barrier.

Here with $ interpolation:

julia> @btime polyeval(2,$v)
  7.856 ns (0 allocations: 0 bytes)
221

julia> @btime reduce((x,y)->x<<1+y, $v; init=0)
  3.825 ns (0 allocations: 0 bytes)
221

julia> @btime evalpoly(2, reverse($v))
  43.112 ns (1 allocation: 64 bytes)
221

julia> @btime mapreduce(((i, v),) -> (v << (i - 1)), |, enumerate(Iterators.reverse($v)))
  13.070 ns (0 allocations: 0 bytes)
221

julia> @btime only(BitVector(reverse($v)).chunks) |> Int
  63.108 ns (3 allocations: 160 bytes)
221

@stevengj I mostly posted my solution for the simplicity. evalpoly is less clear to me than << because I have to think more about about what evalpoly is doing behind the scenes - it’s not a function I use much, where as reduce and << are generic. Of course that will vary person to person.

2 Likes
15

The loop I proposed is exactly the one (with a few modifications) with which the evalpoly function is built.
I did not know of this function (and I think it is not very well known in general).
This is why I believe that @Raf’s solution with reduce is preferable.
On the other hand, I believe that the two functions reduce (…) and poly_2_eval are, in a sense, isomorphic.
They probably have the same lowered code.
In fact, in terms of performance they are practically the same …

julia> v = [true, true, false, true, true, true, false, true]
8-element Vector{Bool}:
 1
 1
 0
 1
 1
 1
 0
 1

julia> function poly_2_eval(p)
           ex = 0
           for e in p
               ex *= 2
               ex+=e
           end
           ex
       end
poly_2_eval (generic function with 1 method)

julia> @btime reduce((x,y)->x<<1+y, $v; init=0)
  4.600 ns (0 allocations: 0 bytes)
221

julia> @btime reduce((x,y)->x*2+y, $v; init=0)
  4.600 ns (0 allocations: 0 bytes)
221

julia> @btime poly_2_eval($v)
  4.200 ns (0 allocations: 0 bytes)
221