StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Let's test it:</p> <pre><code>import collections import math import timeit def power_bit_length(x): return 2**(x-1).bit_length() def shift_bit_length(x): return 1<<(x-1).bit_length() def power_log(x): return 2**(math.ceil(math.log(x, 2))) def test(f): collections.deque((f(i) for i in range(1, 1000001)), maxlen=0) def timetest(f): print('{}: {}'.format(timeit.timeit(lambda: test(f), number=10), f.__name__)) timetest(power_bit_length) timetest(shift_bit_length) timetest(power_log) </code></pre> <p>The reason I'm using <code>range(1, 1000001)</code> instead of just <code>range(1000000)</code> is that the <code>power_log</code> version will fail on <code>0</code>. The reason I'm using a small number of reps over a largeish range instead of lots of reps over a small range is because I expect that different versions will have different performance over different domains. (If you expect to be calling this with huge thousand-bit numbers, of course, you want a test that uses those.)</p> <p>With Apple Python 2.7.2:</p> <pre><code>4.38817000389: power_bit_length 3.69475698471: shift_bit_length 7.91623902321: power_log </code></pre> <p>With Python.org Python 3.3.0:</p> <pre><code>6.566169916652143: power_bit_length 3.098236607853323: shift_bit_length 9.982460380066186: power_log </code></pre> <p>With pypy 1.9.0/2.7.2:</p> <pre><code>2.8580930233: power_bit_length 2.49524712563: shift_bit_length 3.4371240139: power_log </code></pre> <p>I believe this demonstrates that the <code>2**</code> is the slow part here; using <code>bit_length</code> instead of <code>log</code> does speed things up, but using <code>1<<</code> instead of <code>2**</code> is more important.</p> <p>Also, I think it's clearer. The OP's version requires you to make a mental context-switch from logarithms to bits, and then back to exponents. Either stay in bits the whole time (<code>shift_bit_length</code>), or stay in logs and exponents (<code>power_log</code>).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload