229. Copy Set Bits in a Range

Given two non-negative integers m and n, and a range [l, r] (1-indexed, counting bit positions from the least significant bit as position 1), copy every set bit of n that falls within positions l to r (inclusive) into m at those same positions. Bits of m outside the range are left untouched, and bits inside the range where n's corresponding bit is 0 are also left untouched (only 1s are ever copied in, never cleared). Print the resulting value of m.

Input: Four lines: m, n, l, and r, where l and r define the 1-indexed bit-position range (from the LSB) to copy. Output: Print a single integer - the resulting value of m after copying n's set bits within [l, r] into it.

0 <= m, n <= 10^9 1 <= l <= r <= 30

The problem's own rule ('only 1s are ever copied in, never cleared') is exactly why OR (not a full overwrite/assignment) is the correct final step - using OR guarantees m's existing bits outside the copied 1s are never accidentally turned off.

You have two numbers, m and n. You need to copy over just a SPECIFIC range of bit positions from n into m - only turning ON bits that are 1 in n within that range, and leaving everything else in m completely untouched. Brute force: Loop through each bit position from l to r individually, checking if n has that bit set, and if so, explicitly setting the corresponding bit in m one at a time - this works correctly and is actually quite close to the optimized approach, just done position-by-position instead of all at once via a mask. Optimised: Building one combined bitmask for the ENTIRE range [l, r] at once, then using a single AND (to isolate n's relevant bits) followed by a single OR (to merge them into m without disturbing anything else), does the exact same job as looping bit-by-bit, but in just two constant-time bitwise operations instead of a loop.

Iterate over every bit position p from l to r; for each one, check whether bit p of n is set using a shift-and-mask test, and if it is, set bit p of m using a bitwise OR with a single-bit mask at that position. This directly implements the rule of the problem - copy only the 1s from n within the range, leaving everything else in m untouched - and is easy to reason about, but it performs a separate read-and-possibly-write operation for every single bit position in the range instead of handling the whole range at once. Time: O(r - l) Space: O(1)

First loop once over positions l to r to build up a bitmask with exactly those positions set to 1, then perform a single combined update m = m | (n & mask) that copies all of n's set bits within the range into m in one operation. This is correct for the same reason as the brute force, but by separating mask construction from the actual update, m itself is only touched once instead of being read-modified-written once per bit, reducing the number of operations on the target value even though building the mask still takes one pass over the range. Time: O(r - l) Space: O(1)

Compute the range mask directly with a constant number of arithmetic operations - mask = ((1 << (r - l + 1)) - 1) << (l - 1) - which produces exactly the bits from position l to r set to 1 without any iteration, then apply m = m | (n & mask) once. This is correct because shifting a block of all-ones by the right amount is mathematically equivalent to looping bit by bit, but it eliminates the loop entirely, so the whole operation runs in a fixed, small number of steps regardless of how wide the range is. Time: O(1) Space: O(1)

1. Build a 'mask' - a number that has 1s in exactly the bit positions from l to r, and 0s everywhere else. 2. AND that mask with n - this isolates ONLY n's bits that fall within the target range, zeroing out everything else regardless of what n had there. 3. OR that isolated result into m - since OR never turns a bit OFF, this safely adds in the new 1s from n's range without disturbing any of m's existing bits, inside or outside the range. 4. The updated value of m is the final answer.

Time: O(1) - a small, fixed number of bitwise operations, regardless of the size of the range or the numbers involved. Space: O(1) - just the mask and the result, no extra storage needed.

Test l = r (a single bit position) and l = 1, r = 30 (the full allowed range), plus m = 0 or n = 0.

Building a mask for a bit RANGE (not just a single bit) is a genuinely reusable technique - be comfortable constructing `((1 << (r - l + 1)) - 1) << (l - 1)` from first principles rather than memorizing it as an opaque formula.