Copy set bits in a range

The problem, simply

You get two numbers, M and N, and a window of positions from L to R. Positions are counted from 1, starting at the rightmost bit.

For every position inside the window where N has a 1, make that bit of M a 1 too. Never turn a bit of M off, and never touch bits outside the window. Give back the new M.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk through the window one position at a time.

1. For each position i from L to R, make a one bit number bit = 1 << (i - 1).
2. If N & bit is not 0, N has a 1 there, so do M = M | bit.
3. Give back M.

class Solution {
    public static int copySetBits(int m, int n, int l, int r) {
        for (int i = l; i <= r; i++) {
            int bit = 1 << (i - 1);      // positions start at 1, shifts start at 0
            if ((n & bit) != 0) {
                m |= bit;                // switch on the same light in M
            }
        }
        return m;
    }
}

How long it takes: one step per position in the window, O(R - L + 1), which is at most 32 steps. Extra room: O(1).

Way 2: the clever way

Make the cardboard first: a number called a mask, with 1s exactly on positions L to R and 0s everywhere else. Then two bit operations finish the job.

1. (1 << R) - 1 has 1s on positions 1 to R. Taking 1 away from a lone 1 bit turns on every bit below it.
2. (1 << (L - 1)) - 1 has 1s on positions 1 to L - 1, the part we must cut away.
3. XOR the two to keep only positions L to R. That is the mask.
4. N & mask keeps only the 1s of N that show through the hole.
5. M | (N & mask) switches those on in M and leaves every other bit alone.

class Solution {
    public static int copySetBits(int m, int n, int l, int r) {
        long upTo = (1L << r) - 1;          // ones on positions 1 to r
        long below = (1L << (l - 1)) - 1;   // ones on positions 1 to l - 1
        long mask = upTo ^ below;           // ones on positions l to r only
        return (int) (m | (n & mask));      // copy N's ones through the hole
    }
}

How long it takes: a fixed handful of bit operations, O(1). Extra room: one mask, O(1).

Watch out for

• Off by one. Positions in this problem start at 1, but shifts start at 0. Position i is 1 << (i - 1).
• Using ^ or = instead of | when copying. The problem says only switch on. XOR would switch off the bits that are on in both.
• Forgetting the cut. (1 << R) - 1 alone also copies positions below L.

What interviewers ask next

• Copy the window exactly, zeros too? Clear the window in M first, then OR: (M & ~mask) | (N & mask). This is how you write a field into a packed number.
• Toggle all bits of M in the range? M ^ mask.
• Clear all bits of M in the range? M & ~mask.
• Another way to build the mask? ((1L << (R - L + 1)) - 1) << (L - 1): a run of R - L + 1 ones, slid up to position L.
• Check whether all bits in the range are on in N? (N & mask) == mask.

Remember this

Grown-up words: the cardboard with the hole is a bit mask, looking through it is bitwise AND, switching lights on is bitwise OR, and cutting away the lower part is XOR of two masks.