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
    mask = mask || together;        // 1111 1111 1111 1111 0100 0000 0000 0011 <-- mask && mask2
    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