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 modified 4yr ago