Last Updated: 28 Nov, 2021

Copy Bits in Range

Moderate

Asked in companies

Solve now

Problem statement

Ninja is learning the binary representation and bit manipulation. He found an interesting question but had no hints on how to solve it. The question statement says two numbers, ‘A’ and ‘B’ are given, and a range ‘X’ to ‘Y’ is given. You have to copy the set bits of ‘A’ in the range ‘X’ to ‘Y’ in ‘B’ and print the modified value of ‘B’.Can you help Ninja in solving this problem?

For Example

If ‘A’ is 13(1101) and ‘B’ is 7(0111), and the range is 2 to 4. So, we will copy the set bits in the range 2 to 4 from the left. The set bits in this range are the 3rd bit and the 4th bit. So, we will copy these bits to ‘B’.Now, the modified B will be 15(1111) as we copied the 4th bit.

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains four integers, ‘A’ and ‘B’, and the range ‘X’ and ‘Y.’

Output Format:

For each test case, print ‘an integer corresponding to the modified value of ‘B’.

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= ‘A’,’B’ <= 10^9.
1 <= ‘X’,’Y’ <= 30.

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will simply iterate in the range ‘X’ to ‘Y’ and find if the bit is set in ‘A’ or not. If the bit is set, we will copy the corresponding bit in ‘B,’ and at last, we will return the modified B.

Algorithm:

For i in range X to Y, do the following:
- If ( A & 1<<(i-1)) is greater than 0:
  - It implies the ith bit is set in ‘A’.
  - Modify ‘B’ as ‘B’ | (1<<(i-1)).
Return ‘B’.

Solve now

02 Approach

In this approach, we will prepare a bitmask with all the set bits that had to be copied in ‘B’.We will first make an ‘ALL_SET_MASK’ integer with all the bits set in the range ‘X’ to ‘Y’.Now, we will create the final bitmask ‘MASK’ with only the set bits of ‘A’ for the given range as ‘MASK’ = ‘ALL_SET_MASK’ || ‘A’ as it excludes all the unset bits from the ‘ALL_SET_MASK’.

We will simply copy the bits in ‘B’ as B = ‘B’ || ‘MASK’.

At last, return the modified ‘B’.

Algorithm:

Declare ‘ALL_SET_MASK’ to store the integer with all the bits set in the range ‘X’ to ‘Y’.
Set ‘ALL_SET_MASK’ as (1<<(Y) - 1)-(1<<(R-1)-1).
Declare ‘ALL_SET_MASK’ to store the integer with all the bits that had to be copied in ‘B’.
Set ‘MASK’ as bitwise OR of ‘ALL_SET_MASK’ and ‘A’.
Modify ‘B’ as bitwise OR of ‘MASK’ and ‘B’.
Return ‘B’.

Solve now