title: Compute fast log base 2 ceiling in python
body: <p>for given <code>x &lt; 10^15</code>, quickly and accurately determine the maximum integer <code>p</code> such that <code>2^p &lt;= x</code> </p>
  
  <p>Here are some things I've tried:</p>
  
  <p>First I tried this but it's not accurate for large numbers:</p>
  
  <pre><code>&gt;&gt;&gt; from math import log
  &gt;&gt;&gt; x = 2**3
  &gt;&gt;&gt; x
  8
  &gt;&gt;&gt; p = int(log(x, 2))
  &gt;&gt;&gt; 2**p == x
  True
  &gt;&gt;&gt; x = 2**50
  &gt;&gt;&gt; p = int(log(x, 2))
  &gt;&gt;&gt; 2**p == x #not accurate for large numbers?
  False
  </code></pre>
  
  <p>I could try something like:</p>
  
  <pre><code>p = 1
  i = 1
  while True:
      if i * 2 &gt; n:
          break
      i *= 2
      p += 1
      not_p = n - p
  </code></pre>
  
  <p>Which would take up to 50 operations if p was 50</p>
  
  <p>I could pre-compute all the powers of 2 up until 2^50, and use binary search to find p. This would take around log(50) operations but seems a bit excessive and ugly?</p>
  
  <p>I found this thread for C based solutions: <a href="https://stackoverflow.com/questions/3272424/compute-fast-log-base-2-ceiling">Compute fast log base 2 ceiling</a></p>
  
  <p>However It seems a bit ugly and I wasn't exactly sure how to convert it to python.</p>