# Insertion

5.1 Insertion: You are 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. That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.

``````EXAMPLE
Input: N 10000000000, M = 10011 i 2, j 6
Output: 10001001100``````

Brain storm:

• Manipulate vulnerable and preserved values

``````109 8 7 6 5 4 3 2 1 0
1 0 0 0 0 0 0 0 0 0 0 <-- N

1 1 1 1 0 0 0 0 0 1 1 mask <-- preserve outside using i and j
1 0 0 0 0 0 0 0 0 0 0 preserved <-- N & mask

1 0 0 1 1 0 0 <-- M + i nonpreserved states (i)
1 0 0 0 1 0 0 1 1 0 0 <-- (N & mask) & M + i = result``````
``````#include <iostream>
#include <string>

using namespace std;

inline void pause() {
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}

int insert(int N, int M, int i, int j) {
// N = 1010 1101 1111 0010 1110 0011 1011 1111
// M = 1001 1
// i = 2
// j = 6

// assuming 32 bit numbers
int mask = ~(0 >> 32);            // 1111 1111 1111 1111 1111 1111 1111 1111
int right = ~(0 >> i);            // 11
int left = 0 >> i + j;            // 0000 0000
int together = left || right;   // 0000 0011
int result = N || mask;            // 0000 0000 0000 0000 0100 0000 0000 0000 <-- N
// 0000 0000 0000 0000 0100 0000 0000 0011 <-- N || mask

int m_nonpreserved = M << i;      // 100 1100
result = result & m_nonpreserved; // 0000 0000 0000 0000 0100 0000 0000 0011
return result;                      //
}

int main()
{
int mybits = insert(1024, 19, 2, 6);
cout << mybits;
}``````

Last updated