Dados dos números de 32 bits, N y M, y posiciones de dos bits, i y j. Escriba un método para insertar M en N tal que M comience en el bit j y termine en el bit i. Puede suponer que los bits j a i tienen suficiente espacio para caber todo M. Suponiendo que el índice comience desde 0.
Ejemplos:
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)
Este problema ya se ha comentado en el post anterior . En esta publicación, se discute un enfoque diferente.
Enfoque: La idea es muy sencilla, el siguiente es el procedimiento paso a paso:
- Captura todos los bits antes de i en N, es decir desde i-1 hasta 0.
- No queremos alterar esos bits, así que los capturaremos y los usaremos más tarde.
- Borrar todos los bits de j a 0
- Inserte M en N en la posición j a i
- Inserte los bits capturados en su posición respectiva, es decir. de i-1 a 0
Intentemos resolver el ejemplo b para una explicación clara del procedimiento.
Captura de bits i-1 a 0 en N:
Cree una máscara cuyos bits i-1 a 0 sean 1 y el resto sean 0. Cambie 1 a la posición i a la izquierda y reste 1 de esto para obtener una máscara de bits que tenga i-1 a 0 conjunto de bits.
capture_mask = ( 1 << i ) - 1
Entonces, por ejemplo b, la máscara será:
capture_mask = ( 1 << 3 ) - 1 Now capture_mask = 1(001)
Ahora Y esta máscara con N, los bits i-1 a 0 seguirán siendo los mismos mientras que los bits restantes se convertirán en 0. Por lo tanto, nos quedamos solo con los bits i-1 a 0.
captured_bits = N & capture_mask
por ejemplo b, los bits capturados serán:
captured_bits = N & capture_mask Now capture_mask = 1 (001)
Borrado de bits de j a 0 en N:
Como se han capturado los bits, borre los bits j a 0 sin perder los bits i-1 a 0. Cree una máscara cuyos bits j a 0 sean 0 mientras que el resto sea 1. Cree dicha máscara cambiando -1 a la posición j+1 a la izquierda.
clear_mask = -1 << ( j + 1 )
Ahora para borrar los bits j a 0, Y enmascarar con N.
N &= clear_mask
Por ejemplo b será:
N &= clear_mask Now N = 1152 (10010000000)
Insertando M en N:
Ahora, debido a que N tiene bits de j a 0 borrados, simplemente ajuste M en N y cambie la posición de M i a la izquierda para alinear el MSB de M con la posición j en N.
M <<= i
por ejemplo b-
M <<= 3 Now M = 8 << 3 = 64 (1000000)
Haga un OR de M con N para insertar M en la posición deseada.
N |= M
Por ejemplo b-
N |= M Now N = 1152 | 64 = 1216 (10011000000)
Insertar bits capturados en N:
Hasta ahora, M se ha insertado en N. Ahora lo único que queda es volver a fusionar los bits capturados en la posición i-1 a 0. Esto se puede hacer simplemente con OR de N y bits capturados:
N |= captured_bits
Por ejemplo b-
N |= captured_bits N = 1216 | 1 = 1217 (10011000001)
Entonces, finalmente, después de la inserción, se obtiene el siguiente conjunto de bits.
N(before) = 1201 (10010110001) N(after) = 1201 (10011000001)
A continuación se muestra la implementación del enfoque anterior:
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)