Inserting M into N such that m starts at bit j and ends at bit i | Set-2

0 0 8 minutes read

Given two 32-bit numbers, N and M, and two-bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space to fit all of M. Assuming index start from 0.
Examples:

a)  N = 1024 (10000000000),
    M = 19 (10011),
    i = 2, j = 6 
    Output : 1100 (10001001100)
b)  N = 1201 (10010110001)
    M = 8 (1000)
    i = 3, j = 6
    Output: 1217 (10011000001)

This problem has been already discussed in the previous post. In this post, a different approach is discussed.
Approach: The idea is very straightforward, following is the stepwise procedure –

Capture all the bits before i in N, that is from i-1 to 0.
We don’t want to alter those bits so we will capture them and use later
Clear all bits from j to 0
Insert M into N at position j to i
Insert captured bits at their respective position ie. from i-1 to 0

Let’s try to solve example b for a clear explanation of the procedure.

Capturing bits i-1 to 0 in N:
Create a mask whose i-1 to 0 bits are 1 and rest are 0. Shift 1 to i position in left and subtract 1 from this to get a bit mask having i-1 to 0 bits set.

capture_mask = ( 1 << i ) - 1

So for example b, mask will be –

capture_mask = ( 1 << 3 ) - 1 
Now capture_mask = 1(001)

Now AND this mask with N, i-1 to 0 bits will remain same while rest bits become 0. Thus we are left with i-1 to 0 bits only.

captured_bits = N & capture_mask

for example b, captured bits will be –

captured_bits = N & capture_mask
Now capture_mask = 1 (001)

Clearing bits from j to 0 in N:
Since bits have been captured, clear the bits j to 0 without losing bits i-1 to 0. Create a mask whose j to 0 bits are 0 while the rest are 1. Create such mask by shifting -1 to j+1 position in left.

clear_mask = -1 << ( j + 1 )

Now to clear bits j to 0, AND mask with N.

N  &= clear_mask

For example b will be:

N &= clear_mask 
Now N = 1152 (10010000000)

Inserting M in N:

Now because N has bits from j to 0 cleared, just fit in M into N and shift M i position to left to align the MSB of M with position j in N.

M <<= i

For example b-

M <<= 3
Now M = 8 << 3 = 64 (1000000)

Do a OR of M with N to insert M at desired position.

N |= M

For example b –

N |= M 
Now N = 1152 | 64 = 1216 (10011000000)

Inserting captured bits into N:

Till now M has been inserted into N. Now the only thing left is merging back the captured bits at position i-1 to 0. This can be simply done by OR of N and captured bits –

N |= captured_bits

For example b –

N |= captured_bits
N = 1216 | 1 = 1217 (10011000001)

So finally after insertion, the below bitset is obtained.

N(before) = 1201 (10010110001)
N(after) = 1201 (10011000001)

Below is the implementation of the above approach:

C++

// C++ program to insert 32-bit number
// M into N using bit magic
#include <bits/stdc++.h>
using namespace std;
 
// print binary representation of n
void bin(unsigned n)
{
    if (n > 1)
        bin(n / 2);
    printf("%d", n % 2);
}
 
// Insert m into n
int insertion(int n, int m, int i, int j)
{
    int clear_mask = -1 << (j + 1);
    int capture_mask = (1 << i) - 1;
 
    // Capturing bits from i-1 to 0
    int captured_bits = n & capture_mask;
 
    // Clearing bits from j to 0
    n &= clear_mask;
 
    // Shifting m to align with n
    m = m << i;
 
    // Insert m into n
    n |= m;
 
    // Insert captured bits
    n |= captured_bits;
 
    return n;
}
 
// Driver Code
int main()
{
 
    // print original bitset
    int N = 1201, M = 8, i = 3, j = 6;
    cout << "N = " << N << "(";
    bin(N);
    cout << ")"
         << "\n";
 
    // print original bitset
    cout << "M = " << M << "(";
    bin(M);
    cout << ")"
         << "\n";
 
    // Call function to insert M to N
    N = insertion(N, M, i, j);
    cout << "After inserting M into N from 3 to 6"
         << "\n";
 
    // Print the inserted bitset
    cout << "N = " << N << "(";
    bin(N);
    cout << ")"
         << "\n";
    return 0;
}

Java

// Java program to insert
// 32-bit number M into N
// using bit magic
import java.io.*;
 
class GFG
{
     
// print binary 
// representation of n
static void bin(long n)
{
    if (n > 1)
        bin(n / 2);
    System.out.print(n % 2);
}
 
// Insert m into n
static int insertion(int n, int m, 
                     int i, int j)
{
    int clear_mask = -1 << (j + 1);
    int capture_mask = (1 << i) - 1;
 
    // Capturing bits from i-1 to 0
    int captured_bits = n & capture_mask;
 
    // Clearing bits from j to 0
    n &= clear_mask;
 
    // Shifting m to align with n
    m = m << i;
 
    // Insert m into n
    n |= m;
 
    // Insert captured bits
    n |= captured_bits;
 
    return n;
}
 
// Driver Code
public static void main (String[] args) 
{
    // print original bitset
    int N = 1201, M = 8, i = 3, j = 6;
    System.out.print("N = " + N + "(");
    bin(N);
    System.out.println(")");
     
    // print original bitset
    System.out.print("M = " + M + "(");
    bin(M);
    System.out.println(")");
     
    // Call function to insert M to N
    N = insertion(N, M, i, j);
    System.out.println( "After inserting M " + 
                        "into N from 3 to 6");
     
    // Print the inserted bitset
    System.out.print("N = " + N + "(");
    bin(N);
    System.out.println(")");
}
}
 
// This code is contributed 
// by inder_verma.

Python3

# Python 3 program to insert 32-bit number 
# M into N using bit magic
 
# insert M into N
def insertion(n, m, i, j):
 
    clear_mask = -1 << (j + 1)
    capture_mask = (1 << i) - 1
 
    # Capturing bits from i-1 to 0
    captured_bits = n & capture_mask 
 
    # Clearing bits from j to 0
    n &= clear_mask
 
    # Shifting m to align with n
    m = m << i
 
    # Insert m into n
    n |= m 
 
    # Insert captured bits
    n |= captured_bits
 
    return n
 
# Driver
def main():
    N = 1201; M = 8; i = 3; j = 6
    print("N = {}({})".format(N, bin(N)))
    print("M = {}({})".format(M, bin(M)))
    N = insertion(N, M, i, j)
    print("***After inserting M into N***")
    print("N = {}({})".format(N, bin(N)))
 
if __name__ == '__main__':
    main() 

C#

// C# program to insert
// 32-bit number M into N
// using bit magic
using System;
 
class GFG
{
     
// print binary 
// representation of n
static void bin(long n)
{
    if (n > 1)
        bin(n / 2);
    Console.Write(n % 2);
}
 
// Insert m into n
static int insertion(int n, int m, 
                     int i, int j)
{
    int clear_mask = -1 << (j + 1);
    int capture_mask = (1 << i) - 1;
 
    // Capturing bits from i-1 to 0
    int captured_bits = n & capture_mask;
 
    // Clearing bits from j to 0
    n &= clear_mask;
 
    // Shifting m to align with n
    m = m << i;
 
    // Insert m into n
    n |= m;
 
    // Insert captured bits
    n |= captured_bits;
 
    return n;
}
 
// Driver Code
static public void Main (String []args) 
{
    // print original bitset
    int N = 1201, M = 8, i = 3, j = 6;
    Console.Write("N = " + N + "(");
    bin(N);
    Console.WriteLine(")");
     
    // print original bitset
    Console.Write("M = " + M + "(");
    bin(M);
    Console.WriteLine(")");
     
    // Call function to 
    // insert M to N
    N = insertion(N, M, i, j);
    Console.WriteLine("After inserting M " + 
                      "into N from 3 to 6");
     
    // Print the inserted bitset
    Console.Write("N = " + N + "(");
    bin(N);
    Console.WriteLine(")");
}
}
 
// This code is contributed
// by Arnab Kundu

PHP

<?php 
// PHP program to insert 32-bit number
// M into N using bit magic
 
// print binary representation of n
function bin($n)
{
    if ($n > 1)
        bin($n / 2);
    echo $n % 2;
}
 
// Insert m into n
function insertion($n, $m, $i, $j)
{
    $clear_mask = -1 << ($j + 1);
    $capture_mask = (1 << $i) - 1;
 
    // Capturing bits from i-1 to 0
    $captured_bits = $n & $capture_mask;
 
    // Clearing bits from j to 0
    $n &= $clear_mask;
 
    // Shifting m to align with n
    $m = $m << $i;
 
    // Insert m into n
    $n |= $m;
 
    // Insert captured bits
    $n |= $captured_bits;
 
    return $n;
}
 
// Driver Code
 
// print original bitset
$N = 1201;
$M = 8;
$i = 3;
$j = 6;
echo "N = " . $N ."(";
bin($N);
echo ")" ."\n";
 
// print original bitset
echo "M = " . $M ."(";
bin($M);
echo ")". "\n";
 
// Call function to insert M to N
$N = insertion($N, $M, $i, $j);
echo "After inserting M into N " .
              "from 3 to 6" ."\n";
 
// Print the inserted bitset
echo "N = " . $N . "(";
bin($N);
echo ")". "\n";
 
// This code is contributed 
// by ChitraNayal
?>

Javascript

<script>
// Javascript program to insert
// 32-bit number M into N
// using bit magic
     
    // print binary 
// representation of n
    function bin(n)
    {
        if (n > 1)
            bin(Math.floor(n / 2));
        document.write(n % 2);
    }
     
    // Insert m into n
    function insertion(n,m,i,j)
    {
        let clear_mask = -1 << (j + 1);
    let capture_mask = (1 << i) - 1;
   
    // Capturing bits from i-1 to 0
    let captured_bits = n & capture_mask;
   
    // Clearing bits from j to 0
    n &= clear_mask;
   
    // Shifting m to align with n
    m = m << i;
   
    // Insert m into n
    n |= m;
   
    // Insert captured bits
    n |= captured_bits;
   
    return n;
    }
     
    // Driver Code
     
    // print original bitset
    let N = 1201, M = 8, i = 3, j = 6;
    document.write("N = " + N + "(");
    bin(N);
    document.write(")<br>");
       
    // print original bitset
    document.write("M = " + M + "(");
    bin(M);
    document.write(")<br>");
       
    // Call function to insert M to N
    N = insertion(N, M, i, j);
    document.write( "After inserting M " + 
                        "into N from 3 to 6<br>");
       
    // Print the inserted bitset
    document.write("N = " + N + "(");
    bin(N);
    document.write(")<br>");
     
     
     
// This code is contributed by rag2127
</script>

Output:

N = 1201(10010110001)
M = 8(1000)
After inserting M into N from 3 to 6
N = 1217(10011000001)

Time complexity: O(log(M)+log(N))=O(log(M*N)
Auxiliary space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!