title: Times-two faster than bit-shift, for Python 3.x integers?
body: <p>I was looking at the source of <a href="https://github.com/grantjenks/sorted_containers/blob/master/sortedcontainers/sortedlist.py" rel="noreferrer">sorted_containers</a> and was surprised to see <a href="https://github.com/grantjenks/sorted_containers/blob/master/sortedcontainers/sortedlist.py#L72" rel="noreferrer">this line</a>:</p>
  
  <pre><code>self._load, self._twice, self._half = load, load * 2, load &gt;&gt; 1
  </code></pre>
  
  <p>Here <code>load</code> is an integer. Why use bit shift in one place, and multiplication in another? It seems reasonable that bit shifting may be faster than integral division by 2, but why not replace the multiplication by a shift as well? I benchmarked the the following cases:</p>
  
  <ol>
  <li>(times, divide)</li>
  <li>(shift, shift)</li>
  <li>(times, shift)</li>
  <li>(shift, divide)</li>
  </ol>
  
  <p>and found that #3 is consistently faster than other alternatives:</p>
  
  <pre><code># self._load, self._twice, self._half = load, load * 2, load &gt;&gt; 1
  
  import random
  import timeit
  import pandas as pd
  
  x = random.randint(10 ** 3, 10 ** 6)
  
  def test_naive():
      a, b, c = x, 2 * x, x // 2
  
  def test_shift():
      a, b, c = x, x &lt;&lt; 1, x &gt;&gt; 1    
  
  def test_mixed():
      a, b, c = x, x * 2, x &gt;&gt; 1    
  
  def test_mixed_swapped():
      a, b, c = x, x &lt;&lt; 1, x // 2
  
  def observe(k):
      print(k)
      return {
          'naive': timeit.timeit(test_naive),
          'shift': timeit.timeit(test_shift),
          'mixed': timeit.timeit(test_mixed),
          'mixed_swapped': timeit.timeit(test_mixed_swapped),
      }
  
  def get_observations():
      return pd.DataFrame([observe(k) for k in range(100)])
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/mrSuI.png" rel="noreferrer"><img src="https://i.stack.imgur.com/mrSuI.png" alt="enter image description here"></a>
  <a href="https://i.stack.imgur.com/Yo4wL.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Yo4wL.png" alt="enter image description here"></a></p>
  
  <p>The question:</p>
  
  <p>Is my test valid? If so, why is (multiply, shift) faster than (shift, shift)?</p>
  
  <p>I run Python 3.5 on Ubuntu 14.04.</p>
  
  <p><strong>Edit</strong></p>
  
  <p>Above is the original statement of the question. Dan Getz provides an excellent explanation in his answer.</p>
  
  <p>For the sake of completeness, here are sample illustrations for larger <code>x</code> when multiplication optimizations do not apply.</p>
  
  <p><a href="https://i.stack.imgur.com/2btSH.png" rel="noreferrer"><img src="https://i.stack.imgur.com/2btSH.png" alt="enter image description here"></a>
  <a href="https://i.stack.imgur.com/ItTVG.png" rel="noreferrer"><img src="https://i.stack.imgur.com/ItTVG.png" alt="enter image description here"></a></p>