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. >>> >>>
