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
On Tuesday, October 6, 2015 at 9:14:52 PM UTC+5:30, 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 ;-)
>
>
> On Tuesday, October 6, 2015 at 11:41:03 AM UTC-4, Tim Holy wrote:
>>
>> Presumably, iterating over x>>1 until x == 0 should do the trick?
>>
>> --Tim
>>
>> On Tuesday, October 06, 2015 08:21:35 AM Scott Jones wrote:
>> > 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!
>> >
>> > On Tuesday, October 6, 2015 at 11:03:03 AM UTC-4, Steven G. Johnson
>> wrote:
>> > > 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.
>>
>>
