2.2 KiB

Raw Permalink Blame History

5.1. Insertion

You're given 2 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.

Assume that bits j through i have enough space to fit all of M. If M=10011, you can assume there are at least 5 bits between j and i.

Example:

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

Initial idea

I guess we have to update bits starting at j (from N). Reusing the update function from README.md. Probably wrong but idea is to update all bits of M iteratively. O(M).

int insertBit(int N, int M, int j) {
    String newM = Integer.toBinaryString(M);
    for(size_t it = 0; it < newM.length; it++){
        int value = int(it) ? 1 : 0;
        int mask = ~(1 << j);
        N += int((num & mask) | (value << j));
    }
    return N;
}

Another idea could be to slice up N into [:j] and [i+1:]. and then slice_1 + M + slice_2. But this would have to be done in string mode, I think the focus here is doing it with int?

Hint 1

Focus first on clearing the appropriate bits

This is included in the update function I used before.

Hint 2

To clear bits, create a 'bit mask' that looks like a series of 1s, then 0s, then 1s.

int mask = (1 << X) + (0 << (j-i+1)) + (1 << i);

How to get size of N? it says 32 bits but in the example there were 10.

N = int(N & mask) | (M << j) or something.

Hint 3

To create the mask, create a bit mask for the left side, and another one for the right side. Then merge

I think I've done that already.

Solution

Clear bits j through i in N: mask
Shift M so that it lines up with bits j through i
Merge M and N

int updateBits(int n, int m, int i, int j) {
    if (i > j || i < 0 || j >= 32) return 0; // forgot to add this

    /*
    Create mask to clear bits i through j in n.
    if i=2, and j=4, it should look like 11100011.
    For simplicity we use 8 bits for the example
    */
    int allOnes = ~0;

    // 11100000
    int left = j < 31 ? (allOnes << (j+1)) : 0;
    // 00000011
    int right = ((1 << i) - 1);

    int mask = left | right;

    // clear bits j through i and then put m in there
    int n_cleared = n & mask;
    int m_shifted = m << i;

    return n_cleared | m_shifted;
}

2.2 KiB Raw Permalink Blame History