Log inSign up
mediumGeeksforGeeksNot Started

Copy Set Bits in a Range

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on GeeksforGeeks
Lesson

Problem Statement

Given two integers x and y, and a 1-based bit index range [l, r], copy the set bits (bits with value 1) of y in the range [l, r] into x.

Formally, for every bit position i such that l <= i <= r, if the i-th bit of y is 1, set the i-th bit of x to 1. Leave all other bits of x untouched. Return the resulting value of x.

Example 1 · Example 1: Standard Range:

Input: x = 44, y = 3, l = 1, r = 5
Output: 47
Explanation: x = 44 (binary 101100), y = 3 (binary 000011). In range [1, 5], set bits in y are at positions 1 and 2. Setting these in x gives 101111 (binary 47).

Example 2 · Example 2: Single Bit Position:

Input: x = 16, y = 2, l = 1, r = 3
Output: 18
Explanation: x = 16 (10000_2), y = 2 (00010_2). In range [1, 3], bit 2 is set in y. Setting bit 2 in x gives 18 (10010_2).

Constraints:

  • 1 <= x, y <= 109
  • 1 <= l <= r <= 32

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master programmatic creation of arbitrary range bitmasks.
  • Understand bitwise isolation (&) and non-destructive merging (|).
  • Avoid undefined behavior and overflow during bit-shift operations on 32-bit integers.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Perform bit modification restricted to a contiguous subsegment of bit indices [l, r].
  • Copying or transferring bits from one integer to another.
  • Constant-time bitmask synthesis.

Algorithmic Decision Tree:

  • Construct mask = ((1ULL << (r - l + 1)) - 1) << (l - 1).
  • Apply x |= (y & mask).

Connected Patterns:

Count Set BitsReverse BitsHamming Distance

1. Bit-by-Bit Linear Scan

Intuition

Loop through each bit position i from l to r. Construct a single-bit probe 1 << (i - 1). If (y & probe) != 0, then activate that bit in x by computing x |= probe.

When to apply: When simplicity and readability across a few bits are preferred.

Algorithm

  1. Step 1: Loop i from l to r.
  2. Step 2: Check if (y & (1 << (i - 1))) != 0.
  3. Step 3: If true, set bit in x: x |= (1 << (i - 1)).
  4. Step 4: Return x.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int copySetBitsBrute(int x, int y, int l, int r) {
6 for (int i = l; i <= r; ++i) {
7 long long bitMask = 1LL << (i - 1);
8 if ((y & bitMask) != 0) {
9 x |= bitMask;
10 }
11 }
12 return x;
13}
14
15int main() {
16 cout << "Brute (44, 3, 1, 5): " << copySetBitsBrute(44, 3, 1, 5) << endl; // 47
17 cout << "Brute (16, 2, 1, 3): " << copySetBitsBrute(16, 2, 1, 3) << endl; // 18
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(r - l + 1)
  • Space complexity: O(1)

2. Two-Step Shift Masking

Intuition

Calculate the span maskLength = r - l + 1. Form a block of ones (1ULL << maskLength) - 1. Shift this block to align with index l - 1. Filter y through the mask and OR the result into x.

When to apply: When avoiding loops, keeping operations purely bitwise.

Algorithm

  1. Step 1: Compute length = r - l + 1.
  2. Step 2: Generate mask = ((1ULL << length) - 1) << (l - 1).
  3. Step 3: Return x | (y & mask).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int copySetBitsBetter(int x, int y, int l, int r) {
6 int length = r - l + 1;
7 unsigned long long mask = ((1ULL << length) - 1ULL) << (l - 1);
8 return x | (y & mask);
9}
10
11int main() {
12 cout << "Better (44, 3, 1, 5): " << copySetBitsBetter(44, 3, 1, 5) << endl; // 47
13 return 0;
14}

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

3. Direct 64-bit Range Bitmasking

Intuition

Construct the bitmask in a single step using 64-bit unsigned integers: mask = ((1ULL << (r - l + 1)) - 1) << (l - 1). Mask the set bits of y and OR into x. This requires zero loops, zero conditional jumps, and executes in a single cycle on modern hardware.

When to apply: Optimal for production code: handles r up to 32 and 64 cleanly without undefined shifts.

Algorithm

  1. Step 1: Compute 64-bit mask: ((1ULL << (r - l + 1)) - 1ULL) << (l - 1).
  2. Step 2: Return x | (y & mask).

Range Mask Generation Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Compute length = r - l + 1 = 5 - 1 + 1 = 5
Visual state
Values and pointers at this exact step
pointers
S
011111
0
↑ aligned mask
Check / comparison
mask = 31 (binary 011111)
Decision / next transition
Align mask by left-shifting (l - 1) = 0 positions. mask = 31.
Why this step matters

Step 1: Compute length = r - l + 1 = 5 - 1 + 1 = 5. Mask of 5 ones: (1 << 5) - 1 = 31 (binary 011111).

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int setSetBit(int x, int y, int l, int r) {
8 if (l < 1 || r > 32 || l > r) return x;
9 unsigned long long mask = ((1ULL << (r - l + 1)) - 1ULL) << (l - 1);
10 return (int)(x | (y & mask));
11 }
12};
13
14int main() {
15 Solution sol;
16 cout << "Optimal (44, 3, 1, 5): " << sol.setSetBit(44, 3, 1, 5) << endl; // 47
17 cout << "Optimal (16, 2, 1, 3): " << sol.setSetBit(16, 2, 1, 3) << endl; // 18
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Loop Bit by BitO(r - l + 1)O(1)Iterate bit position i from l to r. Test if (y & (1 << (i - 1))) != 0, and if so set x |= (1 << (i - 1)).Iterative bit checking loop.
2.Better — Range Mask ConstructionO(1)O(1)Create a mask of (r - l + 1) ones, shift it to (l - 1), and compute x | (y & mask).Bit-shift bounds.
3.Optimal — 64-bit Direct MaskingOptimalO(1)O(1)Use 64-bit integer arithmetic to safely compute the mask without undefined behavior on shift width >= 32.Hardware bitwise AND / OR execution.

Common Pitfalls & Crucial Edge Cases

Shift overflow with 1 << 32

When r - l + 1 == 32, computing 1 << 32 overflows standard 32-bit integers. Use 1ULL or conditional logic.

1-based vs 0-based bit positions

Ensure the offset aligns with the problem statement's 1-indexed specification (l - 1).

Using addition instead of OR

x + (y & mask) is incorrect if x already has set bits in that range because addition causes carries.

Crucial Edge Cases to Validate:

  • l = 1 and r = 32 (Entire 32-bit range) — 1 << 32 causes undefined behavior / shift overflow in 32-bit systems. Must handle full width safely.
  • l == r (Single bit range) — Range is only 1 bit wide; mask must isolate exactly that bit.
  • y has no set bits in range [l, r] — y & mask evaluates to 0, so x remains unchanged.
  • x already has all set bits in range [l, r] — x remains unchanged after bitwise OR.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether the bit positions l and r are 1-indexed or 0-indexed.
  2. Explicitly mention how you guard against 1 << 32 overflow on maximum ranges.
  3. Emphasize the idempotency of bitwise OR for setting bits.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How do you construct a bitmask containing 1s strictly from bit position l to r (1-indexed)?

2.After generating the mask, how are the set bits from y transferred into x without changing other bits?

3.What is the time complexity of copying set bits in range using a bitmask?

Back to DSA Sheet