Fit Binary Int M into Binary Int N

09 April 2015

Problem overview

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

Algorithm analysis

Just grab number M and iterate over it's binary representation fitting each of it's bits inside N between target indexes I and J.

Code in Java

public class FitBinaryIntIntoAnotherBinaryInt {



<span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">main</span><span class="o">(</span><span class="n">String</span><span class="o">[]</span> <span class="n">args</span><span class="o">)</span> <span class="o">{</span>

    <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">1024</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="mi">23</span><span class="o">;</span>

    <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">convertToBinaryString</span><span class="o">(</span><span class="n">n</span><span class="o">));</span>
    <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">convertToBinaryString</span><span class="o">(</span><span class="n">m</span><span class="o">));</span>

    <span class="kt">int</span> <span class="n">z</span> <span class="o">=</span> <span class="n">fitNumInNum</span><span class="o">(</span><span class="n">n</span><span class="o">,</span> <span class="n">m</span><span class="o">,</span> <span class="mi">3</span><span class="o">,</span> <span class="mi">7</span><span class="o">);</span>
    <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">convertToBinaryString</span><span class="o">(</span><span class="n">z</span><span class="o">));</span>

<span class="o">}</span>

<span class="kd">public</span> <span class="kd">static</span> <span class="kt">int</span> <span class="nf">fitNumInNum</span><span class="o">(</span><span class="kt">int</span> <span class="n">n</span><span class="o">,</span> <span class="kt">int</span> <span class="n">m</span><span class="o">,</span> <span class="kt">int</span> <span class="n">i</span><span class="o">,</span> <span class="kt">int</span> <span class="n">j</span><span class="o">)</span> <span class="o">{</span>
     <span class="k">if</span> <span class="o">(</span><span class="n">n</span> <span class="o">&lt;=</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">m</span> <span class="o">&lt;=</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">m</span> <span class="o">&gt;</span> <span class="n">n</span> <span class="o">||</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">i</span><span class="o">)</span> <span class="o">{</span>
      <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>
     <span class="o">}</span>

     <span class="k">if</span> <span class="o">(</span><span class="n">m</span> <span class="o">==</span> <span class="n">n</span><span class="o">)</span> <span class="o">{</span>
       <span class="k">return</span> <span class="n">n</span><span class="o">;</span>
     <span class="o">}</span>

    <span class="kt">int</span> <span class="n">lenM</span> <span class="o">=</span> <span class="n">getBinarySize</span><span class="o">(</span><span class="n">m</span><span class="o">);</span>

     <span class="k">if</span> <span class="o">((</span><span class="n">j</span> <span class="o">-</span> <span class="o">(</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="o">))</span> <span class="o">!=</span> <span class="n">lenM</span><span class="o">)</span> <span class="o">{</span>
       <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>
     <span class="o">}</span>

     <span class="kt">int</span> <span class="n">i0</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>

    <span class="c1">// n = setRangeBits(n, i, j, false);  </span>
     <span class="k">while</span> <span class="o">(</span><span class="n">i</span> <span class="o">&lt;=</span> <span class="n">j</span> <span class="o">&amp;&amp;</span> <span class="n">i0</span> <span class="o">&lt;</span> <span class="n">lenM</span><span class="o">)</span> <span class="o">{</span>
       <span class="n">n</span> <span class="o">=</span> <span class="n">setBit</span><span class="o">(</span><span class="n">n</span><span class="o">,</span> <span class="n">i</span><span class="o">,</span> <span class="n">getBit</span><span class="o">(</span><span class="n">m</span><span class="o">,</span> <span class="n">i0</span><span class="o">));</span>
       <span class="n">i</span><span class="o">++;</span>
       <span class="n">i0</span><span class="o">++;</span>
     <span class="o">}</span>

     <span class="k">return</span> <span class="n">n</span><span class="o">;</span>
    <span class="o">}</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="kt">int</span> <span class="nf">setRangeBits</span><span class="o">(</span><span class="kt">int</span> <span class="n">n</span><span class="o">,</span> <span class="kt">int</span> <span class="n">i</span><span class="o">,</span> <span class="kt">int</span> <span class="n">j</span><span class="o">,</span> <span class="kt">boolean</span> <span class="n">isSet</span><span class="o">)</span> <span class="o">{</span>
     <span class="k">while</span> <span class="o">(</span><span class="n">i</span> <span class="o">&lt;=</span> <span class="n">j</span><span class="o">)</span> <span class="o">{</span>
       <span class="n">n</span> <span class="o">=</span> <span class="n">setBit</span><span class="o">(</span><span class="n">n</span><span class="o">,</span> <span class="n">i</span><span class="o">,</span> <span class="n">isSet</span><span class="o">);</span>
       <span class="n">i</span><span class="o">++;</span>
     <span class="o">}</span>
     <span class="k">return</span> <span class="n">n</span><span class="o">;</span>
    <span class="o">}</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="kt">boolean</span> <span class="nf">getBit</span><span class="o">(</span><span class="kt">int</span> <span class="n">n</span><span class="o">,</span> <span class="kt">int</span> <span class="n">i</span><span class="o">)</span> <span class="o">{</span>
     <span class="k">return</span> <span class="o">((</span><span class="n">n</span> <span class="o">&amp;</span> <span class="o">(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">i</span><span class="o">))</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">);</span>
    <span class="o">}</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="kt">int</span> <span class="nf">setBit</span><span class="o">(</span><span class="kt">int</span> <span class="n">n</span><span class="o">,</span> <span class="kt">int</span> <span class="n">i</span><span class="o">,</span> <span class="kt">boolean</span> <span class="n">isSet</span><span class="o">)</span> <span class="o">{</span>
     <span class="k">if</span> <span class="o">(</span><span class="n">isSet</span><span class="o">)</span> <span class="o">{</span>
       <span class="k">return</span> <span class="n">n</span> <span class="o">|</span> <span class="o">(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">i</span><span class="o">);</span>
     <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
       <span class="k">return</span> <span class="n">n</span> <span class="o">&amp;</span> <span class="o">~(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">i</span><span class="o">);</span>
     <span class="o">}</span>
    <span class="o">}</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="kt">int</span> <span class="nf">getBinarySize</span><span class="o">(</span><span class="kt">int</span> <span class="n">n</span><span class="o">)</span> <span class="o">{</span>
           <span class="kt">int</span> <span class="n">counter</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
         <span class="k">while</span><span class="o">(</span><span class="n">n</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
              <span class="n">counter</span><span class="o">++;</span>
          <span class="n">n</span> <span class="o">=</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="o">;</span>
         <span class="o">}</span>
         <span class="k">return</span> <span class="n">counter</span><span class="o">;</span>
    <span class="o">}</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="n">String</span> <span class="nf">convertToBinaryString</span><span class="o">(</span><span class="kt">int</span> <span class="n">n</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">StringBuilder</span> <span class="n">sb</span> <span class="o">=</span> <span class="k">new</span> <span class="n">StringBuilder</span><span class="o">();</span>

         <span class="k">while</span><span class="o">(</span><span class="n">n</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
          <span class="k">if</span> <span class="o">(</span> <span class="o">(</span><span class="n">n</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="o">)</span> <span class="o">==</span> <span class="mi">1</span><span class="o">)</span> <span class="o">{</span>
           <span class="n">sb</span><span class="o">.</span><span class="na">append</span><span class="o">(</span><span class="s">"1"</span><span class="o">);</span>
          <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
           <span class="n">sb</span><span class="o">.</span><span class="na">append</span><span class="o">(</span><span class="s">"0"</span><span class="o">);</span>
          <span class="o">}</span>

          <span class="n">n</span> <span class="o">=</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="o">;</span>
         <span class="o">}</span>

         <span class="k">return</span> <span class="n">sb</span><span class="o">.</span><span class="na">reverse</span><span class="o">().</span><span class="na">toString</span><span class="o">();</span>
    <span class="o">}</span>




}

Full source code

comments powered by Disqus