Converting bitstring to number

General Usage
1

I know that if I have a litteral bitstring, I can convert it to an integer with

Int(0b110101)

Now, however, I would like to convert a bit string, either given as a tuple of 0 and 1, or as an actual string, to the corresponding integer value. I figured in the tuple case, I could do something like

julia> bits2int(b::Vararg{Integer,N}) where N = sub2ind(ntuple(_->2,Val(N)),reverse(b.+1)...) - 1;

julia> Int(0b110101) == bits2int(1,1,0,1,0,1)
true

However, the above is really slow.

In the string case, I thought it might be possible to do with a string macro, but I am not sure how.

Any suggestions?

Thanks,
Jeremy

2

Using v0.7 / master, it’s simple:
parse(Int, "110101"; base=2)

1 Like
3

Ah right of course. Is it possible to obtain the length of the string in a type stable way (i.e. the length will go in a type parameter) using a string macro?

4

Do you want the length of the string, or the position of the leftmost bit (i.e. without any leading zeros)?

5

The total length including leading zeros.

6

It sounds as if you have the string. The length of that string (its a vanilla string, presumably) is length(string) that returns the number of characters. If your leading zeros are in the string, you are done. If your strings are implicitly left padded with zeros, then you know the length already, you are done. (length(str::AbstractString} is type stable)

1 Like
7

Not if I want to put that length in a type parameter, as I explained:

julia> struct Bits{N}; num::Int; end

julia> Bits(s) = Bits{length(s)}(parse(Int,s,2))
Bits

julia> Bits("110101")
Bits{6}(53)

julia> @code_warntype Bits("110101")
Variables:
  #self# <optimized out>
  s::String

Body:
  begin
      return ((Core.apply_type)(Main.Bits, $(Expr(:invoke, MethodInstance for length(::String), :(Main.length), :(s))))::Type{Bits{_}} where _)($(Expr(:invoke, MethodInstance for parse(::Type{Int64}, ::String, ::Int64), :(Main.parse), :(Main.Int), :(s), 2)))::Bits{_} where _
  end::Bits{_} where _
8

Otherwise, does anyone have an idea with the sub2ind approach is slow?

julia> @btime bits2int(1,1,0,1,0,1)  
  1.403 μs (9 allocations: 240 bytes)
53

edit: slow compared to sub2ind on its own, which is basically instantaneous.

9

Is your goal to accept strings that are a sequence of 1s and 0s and then convert each string as it is available into the corresponding datapair
(stringlength, integer value of parsed string)? and then keep it in a struct

10

Yes, but the length should be a type parameter. Obviously, with a tuple input that length is very easy to obtain as a type parameter. I was wondering if that was possible to also do with a string.

I thought it might be possible with a macro by doing the computation of the length during compilation.

11 
julia> struct BitStrFun{L} # L is the parameter which gets the string length
           value::UInt
           
           function BitStrFun(str::String) where {L}
               value = parse(UInt, string("0b", str))
               nbits = length(str)
               return new{nbits}(value)
           end
       end

julia> a = BitStrFun("11011")
BitStrFun{5}(0x000000000000001b)

julia> a.value
0x000000000000001b

julia> a = BitStrFun("0000000000000101")
BitStrFun{16}(0x0000000000000005)

julia> struct BitStrFun2{L} # L is the parameter which gets the string length
           value::Int
           
           function BitStrFun2(str::String) where {L}
               value = parse(Int, string("0b", str))
               nbits = length(str)
               return new{nbits}(value)
           end
       end

julia> 

julia> a = BitStrFun2("0000000000000101")
BitStrFun2{16}(5)

julia> a.value
5

julia> nbits(x::BitStrFun2{L}) where {L} = L
nbits (generic function with 1 method)

julia> nbits(a)
16
12

note: the above presupposes your strings have only ones and zeros (no leading 0b); if the incoming strings are formatted with a leading 0b just replace value = parse(Int, string(.. with value = parse(Int, str)

13

Yes, you can do this with a string macro:

julia> struct Bits{L}
         value::Int
       end

julia> macro bits_str(bits::String)
           quote
               Bits{$(length(bits))}($(parse(Int, bits, 2)))
           end
       end
@bits_str (macro with 1 method)

julia> bits"1001"
Bits{4}(9)

Since the length computation happens when the macro is expanded, the length is essentially baked into the resulting expression, and the result is type-stable:

julia> f() = bits"1001"
f (generic function with 1 method)

julia> @code_warntype f()
Variables:
  #self# <optimized out>

Body:
  begin 
      # meta: location REPL[1] # line 3:
      SSAValue(0) = $(Expr(:new, Bits{4}, 9))
      # meta: pop location
      return SSAValue(0)
  end::Bits{4}
4 Likes
14

Great thanks! I’m not very experienced with the macro notation so this is helpful :slight_smile:

15

Maybe its a julia version issue, I modified this part into, to get it to work properly (julia v1.4):

Bits{$(length(bits))}($(parse(Int, bits; base=2)))