Bit manipulation modify bits to include number

Question

I am studying for an interview and I have been trying to understand this question for hours now:

You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j).

Could someone give a complete example and walk through what is actually required? Do i need to set the between i and j to form the value of M, or to actually the bits in M?

Is there some good tutorial on bits manipulation which explains the concepts?

Thank you!

Answer 1

Can be achieved using "masking"

• creating a mask for the position i to j with each bit set to 1 using bitwise OR incrementally
• blank out the bits in N using bitwise AND and bitwise NOT of the mask
• select the bits from M using mask with bitwise AND
• copy bits in using bitwise OR

I know I've used hex in my example, but same principle applies, just easier to read.

Example

int n = 0x12345678;
int m = 0x55555555;

int i = 4; // assume right to left
int j = 15;

int mask = 0;
for (int pos = i; pos <= j; pos++) {
    mask = mask | (1 << pos);
}
System.out.println(String.format("mask is     0x%08x", mask));

int nCleared = n & ~mask;
System.out.println(String.format("clear n     0x%08x", nCleared));

int bitsFromM = (m & mask);
System.out.println(String.format("Bits from m 0x%08x", bitsFromM));

int nWithM = bitsFromM | nCleared;
System.out.println(String.format("n with m    0x%08x", nWithM));

Output

mask is     0x0000fff0
clear n     0x12340008
Bits from m 0x00005550
n with m    0x12345558

Answer 2

Let's say those 2 32-bit numbers are :-

M = "00010101010101010101010101010101";
N = "10101010100001010101100101011111";
i = 13;
j = 23;

They just want you to make N's 13th to 23rd bits the same as those in M.

I am counting the positions from the right-hand-side.

                                             23rd bit  13th bit

So,here, M's 13th to 23rd character = "000101010_____ 10101010101 ___010101010101";

is the mid-spaced 10101010101.

Hence, N must be 101010101___ 10101010101 _____100101011111

or N = 101010101 "10101010101" 100101011111.