Inserting M into N such that m starts at bit j and ends at bit i | Set-2
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> |
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)
Contact Us