Copy set bits in a range

Problem Statement

Given two numbers M and N, and a range [L, R] (1-indexed from the right), copy the set bits of N in the given range into M. In other words, set those bits in M that are set in N within positions L to R.

Example:

Noob-Friendly Explanation

Imagine you have two rows of switches (M and N), each numbered from right to left starting at 1. You're told: "Look at switches L through R on row N. Wherever there's an ON switch in row N within that range, turn ON the corresponding switch in row M too."

Important: you only turn ON — you never turn OFF. If M already has a switch ON, it stays ON regardless of N.

So if M = 101011 and N = 111011, and we look at positions 2 to 5:

• N's bits at positions 2-5 are: 1101
• We turn ON those bits in M → M goes from 101011 to 101111

Approach 1: Brute Force (Bit by Bit)

Intuition

Check each bit position from L to R. If that bit is set in N, set it in M using the OR operation.

Algorithm

1. For each position i from L to R:
   • Check if bit at position i is set in N
   • If yes, set that bit in M using M = M | (1 << (i-1))
2. Return M

class Solution {
    public static int copySetBits(int m, int n, int l, int r) {
        for (int i = l; i <= r; i++) {
            int bitPosition = i - 1; // convert to 0-indexed
            // Check if bit is set in N
            if ((n & (1 << bitPosition)) != 0) {
                // Set that bit in M
                m = m | (1 << bitPosition);
            }
        }
        return m;
    }

    public static void main(String[] args) {
        System.out.println(copySetBits(43, 59, 2, 5)); // 47
        System.out.println(copySetBits(0, 15, 1, 4));  // 15
    }
}

Complexity Analysis

• Time Complexity: O(R - L) — We iterate through the range of bits
• Space Complexity: O(1) — Only using a few variables

Approach 2: Optimal (Mask-Based)

Intuition

Instead of checking each bit individually, create a mask that covers the range [L, R], extract those bits from N, and OR them into M in one shot.

The mask for range [L, R] has 1s at positions L through R and 0s everywhere else. We can create this as: ((1 << R) - 1) ^ ((1 << (L-1)) - 1) which is equivalent to ((1 << R) - (1 << (L-1))).

Algorithm

1. Create a range mask: bits L to R are 1, rest are 0
2. Extract N's bits in this range: n & mask
3. OR with M: m = m | (n & mask)

class Solution {
    public static int copySetBits(int m, int n, int l, int r) {
        // Create mask with 1s from position L to R
        // mask = ((1 << r) - 1) - ((1 << (l-1)) - 1)
        // Simplified: bits from L to R are set
        int mask = ((1 << r) - (1 << (l - 1)));

        // Extract N's set bits in the range, then OR into M
        m = m | (n & mask);

        return m;
    }

    public static void main(String[] args) {
        System.out.println(copySetBits(43, 59, 2, 5)); // 47
        System.out.println(copySetBits(0, 15, 1, 4));  // 15
        System.out.println(copySetBits(8, 7, 1, 3));   // 15
    }
}

Complexity Analysis

• Time Complexity: O(1) — Just a few bitwise operations, no loops
• Space Complexity: O(1) — Only using a mask variable

Key Takeaways

1. Range Mask: ((1 << R) - (1 << (L-1))) creates a mask with 1s in positions L to R
2. OR for Setting Bits: M | bits sets those bits in M without disturbing other bits
3. Extract and Apply: n & mask extracts specific bits, then OR them into M
4. 1-indexed vs 0-indexed: Be careful with bit positions — this problem uses 1-indexed positions