title: Given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M
body: <blockquote>
    <p>You are given two 32-bit numbers, N and M, and two bit positions, i
    and j. Write a method to set all bits between i and j in N equal to M
    (e.g., M becomes a substring of N located at i and starting at j).
    EXAMPLE: Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N =
    10001010100</p>
  </blockquote>
  
  <p>This problem is from Cracking the Coding interview. I was able to solve it using the following O(j - i) algorithm:</p>
  
  <pre><code>def set_bits(a, b, i, j):
      if not b: return a
      while i &lt;= j:
          if b &amp; 1 == 1:
              last_bit = (b &amp; 1) &lt;&lt; i
              a |= last_bit
          else:
              set_bit = ~(1 &lt;&lt; i)
              a &amp;= set_bit
          b &gt;&gt;= 1
          i += 1
      return a
  </code></pre>
  
  <p>The author gave this O(1) algorithm as a solution:</p>
  
  <pre><code>def update_bits(n, m, i, j):
      max = ~0 # All 1s
  
      # 1s through position j, then zeroes
      left = max - ((1 &lt;&lt; j) - 1)
  
      # 1s after position i
      right = ((1 &lt;&lt; i) - 1)
  
      # 1’s, with 0s between i and j
      mask = left | right
  
      #  Clear i through j, then put m in there 
      return (n &amp; mask) | (m &lt;&lt; i)
  </code></pre>
  
  <p>I noticed that for some test cases the author's algorithm seems to be outputting the wrong answer. For example for N = 488, M = 5, i = 2, j = 6 it outputs 468. When the output should be 404, as my O(j - i) algorithm does.</p>
  
  <p><strong>Question: Is there a way to get a constant time algorithm which works for all cases?</strong> </p>