Fastest way to get # of bits of an integer value in Julia?

[Scott Jones]

I couldn't find anything yet - is there a recommended / fastest way to get the number of bits in a number (I really only need it for unsigned values).

Thanks

[Steven G. Johnson]

On Tuesday, October 6, 2015 at 10:59:04 AM UTC-4, Scott Jones wrote:

I couldn't find anything yet - is there a recommended / fastest way to get the number of bits in a number (I really only need it for unsigned values).

Thanks

sizeof(number)*8 if you want all the bits (though you'd need to define a separate method for BigInt), or count_ones(number) if you want the 1 bits. 

[Tomas Lycken]

…or ceil(Int, log(2, x)) if you want the number of bits required to represent x as an unsigned integer.

It really depends on what you mean by “the number of bits in a number” :P

// T

[Scott Jones]

Sorry!  I should have been more specific.

What I want is:

0 -> 0

1 -> 1

0x8 -> 4

0x1f -> 5

13 -> 5

i.e. number of bits needed to represent the number.

I want to pack 2 or 3 values into a unsigned int, (maybe a UInt16, up to a UInt128), that I can then use for sorting purposes efficiently.

(much more cache efficient, eliminates a bunch of pointer references, etc.)

Any idea how? (normally, I'd just use the assembly instructions available that do this, but I want to do this in pure Julia [it would be nice if the Julia code

could actually be smart enough to generate the correct native code ;-) )

Thanks!

[Scott Jones]

I'm just afraid that using a log function wouldn't be very fast.

Is that heavily optimized for unsigned integer x?

[Scott Jones]

mistyped there, 13 -> 4.

I just found leading_zeros, not sure how efficient that is, but it might be good enough for now, I can use:

sizeof(x)*8 - leading_zeros(x)

[Tim Holy]

Presumably, iterating over x>>1 until x == 0 should do the trick?

--Tim

[Scott Jones]

Well, I asked about how to get it as fast as possible.

Turns out, leading_zeros does just what I want, using the lzcnt* instruction :-)

If you don't count the unnecessary frame setup (pushq %rbp; movq %rsp, %rbp) and frame pop/return (popq %rbp ; ret), the whole thing I want boils down to 4 instructions, nicely parameterized by Julia on the type ;-)

[Scott Jones]

On Tuesday, October 6, 2015 at 11:44:52 AM UTC-4, Scott Jones wrote:

Well, I asked about how to get it as fast as possible.

Turns out, leading_zeros does just what I want, using the lzcnt* instruction :-)

If you don't count the unnecessary frame setup (pushq %rbp; movq %rsp, %rbp) and frame pop/return (popq %rbp ; ret), the whole thing I want boils down to 4 instructions, nicely parameterized by Julia on the type ;-)

What this means, is that I can take a column index, row index, and input array indices, pack them tightly into a work vector (with indices of zero input values already removed),

that can be sorted very quickly and stably by quicksort (because of using the input array index value, makes there not be any duplicates).

Love the way Julia does a lot of the work I used to have to do by hand for me ;-)

Hat's off, again, to the core team and all the contributors!

[Ravi S]

julia> function nbits(x)
         n = 0
         while x!=0
           n += 1
           x >>= 1
         end;
         return n
       end
nbits (generic function with 1 method)

julia> @time ceil(log2(x))
elapsed time: 7.376e-6 seconds (112 bytes allocated)
18.0

julia> @time sizeof(x)*8 - leading_zeros(x)
elapsed time: 9.781e-6 seconds (80 bytes allocated)
18

julia> @time length(bin(x))
elapsed time: 6.693e-6 seconds (176 bytes allocated)
18

julia> @time nbits(x)
elapsed time: 5.425e-6 seconds (80 bytes allocated)
18

[Jason Merrill]

Ravi, I think you're running into the resolution of your timers there. I suspect all of those operations are much faster than a microsecond.

[Scott Jones]

When benchmarking in Julia, you always have to remember to do things twice, so that you are not measuring the JIT compilation time.

(it can also be a good idea to call gc() just before the timings, if there is significant memory usage).

You also have to be very careful that Julia doesn't simply optimize away benchmark loops completely (hence the trick with returning the value

from the benchmark function)

I got the following:

julia> f1(x) = sizeof(x)<<3 - leading_zeros(x)

f1 (generic function with 1 method)

julia> f2(x) = ceil(log2(x))

f2 (generic function with 1 method)

julia> f3(x) = length(bin(x))

f3 (generic function with 1 method)

julia> function f4(x)

       n = 0

       while x != 0

       n += 1

       x >>= 1

       end

       n

       end

f4 (generic function with 1 method)

julia> ft1(x,n) = (local y ; for i=1:n ; y = f1(x) ; end ; y)

ft1 (generic function with 1 method)

julia> ft2(x,n) = (local y ; for i=1:n ; y = f2(x) ; end ; y)

ft2 (generic function with 1 method)

julia> ft3(x,n) = (local y ; for i=1:n ; y = f3(x) ; end ; y)

ft3 (generic function with 1 method)

julia> ft4(x,n) = (local y ; for i=1:n ; y = f4(x) ; end ; y)

ft4 (generic function with 1 method)

julia> @time ft1(x,1000000)

  0.006164 seconds (4 allocations: 160 bytes)

32

julia> @time ft2(x,1000000)

  0.024435 seconds (1.00 M allocations: 15.259 MB, 8.07% gc time)

31.0

julia> @time ft3(x,1000000)

  0.070985 seconds (2.00 M allocations: 122.070 MB, 7.80% gc time)

32

julia> @time ft4(x,1000000)

  0.027962 seconds (4 allocations: 160 bytes)

3

[Scott Jones]

Also, ceil(log2(n)) doesn't get the correct answer - it gets 31 instead of 32.

(my value of x was 2^31)

On Tuesday, October 6, 2015 at 11:50:19 AM UTC-4, Ravi S wrote:

[Kevin Squire]

It should be floor(log2(n))+1 (excluding zero).