It should be floor(log2(n))+1 (excluding zero). On Tue, Oct 6, 2015 at 9:45 AM, Scott Jones <[email protected]> wrote:
> 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: > >> 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. >>>> >>>>
