Posted on by Kalkicode
Code Bit Logic

# Copy set bits in a range

The given problem is about copying set bits from a specific range of bits in one integer (`b`) to another integer (`a`). We are provided with four inputs: `a`, `b`, `r1`, and `r2`. The goal is to copy all the active (set) bits of `b` from the range `r1` to `r2` and place them in the corresponding positions of `a`.

## Explanation with Example

Let's take an example to understand the problem better:

Suppose `a = 37` (binary representation: 100101) and `b = 27` (binary representation: 011011). We are given the range `r1 = 3` and `r2 = 5`. The range is inclusive, so we need to consider the bits from position 3 to 5 in `b`.

1. The bits to be copied from `b` are `011` (range from position 3 to 5).
2. Now, we need to set these bits in `a` at positions 3 to 5.
3. The modified `a` will be `111101` (binary representation of 61).

## Standard Pseudocode

``````1. copy_bit(a, b, r1, r2):
2.     if r1 < 0 or r2 < 0 or r1 > 31 or r2 > 31:
3.         return // Invalid range
4.     result = ((1 << (r2 - r1 + 1)) - 1) << r1
5.     result = (result & b) | a
6.     return result
``````

## Algorithm Explanation

1. Check if the input ranges `r1` and `r2` are valid (non-negative and less than or equal to 31). If not, return an error indicating an invalid range.
2. Calculate a bitmask `result` to set all the active bits from the range `r1` to `r2`. The bitmask is obtained by shifting 1 to the left by the number of bits in the range and then subtracting 1 from the result. Finally, we shift this bitmask by `r1` positions to place it at the correct range in `a`.
3. Perform a bitwise AND operation between the bitmask `result` and `b` to extract the set bits from `b` within the specified range.
4. Perform a bitwise OR operation between the extracted bits from step 3 and `a` to set the bits in `a` as required.
5. Return the modified value of `a`.

## Code Solution

Here given code implementation process.

``````// C program
// Copy set bits in a range
#include <stdio.h>

// Copy all active bits (B to A) of from given range
void copy_bit(int a, int b, int r1, int r2)
{
if (r1 < 0 || r2 < 0 || r1 > 31 && r2 > 31)
{
// Invalid range
return;
}
printf("\n Given Number (a : %d,b : %d)", a, b);
// Set all active bits of a given range
int result = ((1 << (r2 - r1 + 1)) - 1) << ((r1 - 1));
// Get copy result
result = (result & b) | a;
// Display calculated result
printf("\n Result : %d", result);
}
int main(int argc, char
const *argv[])
{
int a = 37;
int b = 27;
int r1 = 3;
int r2 = 5;
// Test case a
// a = 37 (100101)
// b = 27 (011011)
//          ↓↓↓  (range r1 = 3, r2 = 5)
// result (111101) = 61
copy_bit(a, b, r1, r2);
// Test case b
a = 37;
b = 19;
r1 = 2;
r2 = 5;
// a = 37 (100101)
// b = 19 (010011)
//          ↓↓↓↓ (range r1 = 2, r2 = 5)
// result (110111) (55)
copy_bit(a, b, r1, r2);
return 0;
}``````

#### Output

`````` Given Number (a : 37,b : 27)
Result : 61
Given Number (a : 37,b : 19)
Result : 55``````
``````/*
Java program
Copy set bits in a range
*/
public class BitManipulation
{
// Copy all active bits (B to A) of from given range
public void copyBit(int a, int b, int r1, int r2)
{
if (r1 < 0 || r2 < 0 || r1 > 31 && r2 > 31)
{
// Invalid range
return;
}
System.out.print("\n Given Number (a : " + a + ",b : " + b + ")");
// Set all active bits of a given range
int result = ((1 << (r2 - r1 + 1)) - 1) << ((r1 - 1));
// Get copy result
result = (result & b) | a;
// Display calculated result
System.out.print("\n Result : " + result );
}

public static void main(String[] args)
{
int a = 37;
int b = 27;
int r1 = 3;
int r2 = 5;
// Test case a
// a = 37 (100101)
// b = 27 (011011)
//          ↓↓↓  (range r1 = 3, r2 = 5)
// result (111101) = 61
// Test case b
a = 37;
b = 19;
r1 = 2;
r2 = 5;
// a = 37 (100101)
// b = 19 (010011)
//          ↓↓↓↓ (range r1 = 2, r2 = 5)
// result (110111) (55)

}
}``````

#### Output

`````` Given Number (a : 37,b : 27)
Result : 61
Given Number (a : 37,b : 19)
Result : 55``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ program
Copy set bits in a range
*/

class BitManipulation
{
public:
// Copy all active bits (B to A) of from given range
void copyBit(int a, int b, int r1, int r2)
{
// Invalid range
if (r1 < 0 || r2 < 0 || r1 > 31 && r2 > 31)
{
return;
}
cout << "\n Given Number (a : " << a << ",b : " << b << ")";
// Set all active bits of a given range
int result = ((1 << (r2 - r1 + 1)) - 1) << ((r1 - 1));
// Get copy result
result = (result &b) | a;
// Display calculated result
cout << "\n Result : " << result;
}
};
int main()
{
int a = 37;
int b = 27;
int r1 = 3;
int r2 = 5;
// Test case a
// a = 37 (100101)
// b = 27 (011011)
//          ↓↓↓  (range r1 = 3, r2 = 5)
// result (111101) = 61
// Test case b
a = 37;
b = 19;
r1 = 2;
r2 = 5;
// a = 37 (100101)
// b = 19 (010011)
//          ↓↓↓↓ (range r1 = 2, r2 = 5)
// result (110111) (55)
return 0;
}``````

#### Output

`````` Given Number (a : 37,b : 27)
Result : 61
Given Number (a : 37,b : 19)
Result : 55``````
``````// Include namespace system
using System;
/*
C# program
Copy set bits in a range
*/
public class BitManipulation
{
// Copy all active bits (B to A) of from given range
public void copyBit(int a, int b, int r1, int r2)
{
// Invalid range
if (r1 < 0 || r2 < 0 || r1 > 31 && r2 > 31)
{
return;
}
Console.Write("\n Given Number (a : " + a + ",b : " + b + ")");
// Set all active bits of a given range
int result = ((1 << (r2 - r1 + 1)) - 1) << ((r1 - 1));
// Get copy result
result = (result & b) | a;
// Display calculated result
Console.Write("\n Result : " + result);
}
public static void Main(String[] args)
{
int a = 37;
int b = 27;
int r1 = 3;
int r2 = 5;
// Test case a
// a = 37 (100101)
// b = 27 (011011)
//          ↓↓↓  (range r1 = 3, r2 = 5)
// result (111101) = 61
// Test case b
a = 37;
b = 19;
r1 = 2;
r2 = 5;
// a = 37 (100101)
// b = 19 (010011)
//          ↓↓↓↓ (range r1 = 2, r2 = 5)
// result (110111) (55)
}
}``````

#### Output

`````` Given Number (a : 37,b : 27)
Result : 61
Given Number (a : 37,b : 19)
Result : 55``````
``````<?php
/*
Php program
Copy set bits in a range
*/
class BitManipulation
{
// Copy all active bits (B to A) of from given range
public	function copyBit(\$a, \$b, \$r1, \$r2)
{
// Invalid range
if (\$r1 < 0 || \$r2 < 0 || \$r1 > 31 && \$r2 > 31)
{
return;
}
echo "\n Given Number (a : ". \$a .",b : ". \$b .")";
// Set all active bits of a given range
\$result = ((1 << (\$r2 - \$r1 + 1)) - 1) << ((\$r1 - 1));
// Get copy result
\$result = (\$result & \$b) | \$a;
// Display calculated result
echo "\n Result : ". \$result;
}
}

function main()
{
\$a = 37;
\$b = 27;
\$r1 = 3;
\$r2 = 5;
// Test case a
// a = 37 (100101)
// b = 27 (011011)
//          ↓↓↓  (range r1 = 3, r2 = 5)
// result (111101) = 61
// Test case b
\$a = 37;
\$b = 19;
\$r1 = 2;
\$r2 = 5;
// a = 37 (100101)
// b = 19 (010011)
//          ↓↓↓↓ (range r1 = 2, r2 = 5)
// result (110111) (55)
}
main();``````

#### Output

`````` Given Number (a : 37,b : 27)
Result : 61
Given Number (a : 37,b : 19)
Result : 55``````
``````/*
Node Js program
Copy set bits in a range
*/
class BitManipulation
{
// Copy all active bits (B to A) of from given range
copyBit(a, b, r1, r2)
{
// Invalid range
if (r1 < 0 || r2 < 0 || r1 > 31 && r2 > 31)
{
return;
}
process.stdout.write("\n Given Number (a : " + a + ", b : " + b + ")");
// Set all active bits of a given range
var result = ((1 << (r2 - r1 + 1)) - 1) << ((r1 - 1));
// Get copy result
result = (result & b) | a;
// Display calculated result
process.stdout.write("\n Result : " + result);
}
}

function main()
{
var a = 37;
var b = 27;
var r1 = 3;
var r2 = 5;
// Test case a
// a = 37 (100101)
// b = 27 (011011)
//          ↓↓↓  (range r1 = 3, r2 = 5)
// result (111101) = 61
// Test case b
a = 37;
b = 19;
r1 = 2;
r2 = 5;
// a = 37 (100101)
// b = 19 (010011)
//          ↓↓↓↓ (range r1 = 2, r2 = 5)
// result (110111) (55)
}
main();``````

#### Output

`````` Given Number (a : 37, b : 27)
Result : 61
Given Number (a : 37, b : 19)
Result : 55``````
``````#   Python 3 program
#   Copy set bits in a range

class BitManipulation :
#  Copy all active bits (B to A) of from given range
def copyBit(self, a, b, r1, r2) :
if (r1 < 0 or r2 < 0 or r1 > 31 and r2 > 31) :
#  Invalid range
return

print("\n Given Number (a : ", a ,",b : ", b ,")", end = "")
#  Set all active bits of a given range
result = ((1 << (r2 - r1 + 1)) - 1) << ((r1 - 1))
#  Get copy result
result = (result & b) | a
#  Display calculated result
print("\n Result : ", result, end = "")

def main() :
a = 37
b = 27
r1 = 3
r2 = 5
#  Test case a
#  a = 37 (100101)
#  b = 27 (011011)
#           ↓↓↓  (range r1 = 3, r2 = 5)
#  result (111101) = 61
#  Test case b
a = 37
b = 19
r1 = 2
r2 = 5
#  a = 37 (100101)
#  b = 19 (010011)
#           ↓↓↓↓ (range r1 = 2, r2 = 5)
#  result (110111) (55)

if __name__ == "__main__": main()``````

#### Output

`````` Given Number (a :  37 ,b :  27 )
Result :  61
Given Number (a :  37 ,b :  19 )
Result :  55``````
``````#   Ruby program
#   Copy set bits in a range

class BitManipulation
#  Copy all active bits (B to A) of from given range
def copyBit(a, b, r1, r2)
if (r1 < 0 || r2 < 0 || r1 > 31 && r2 > 31)
#  Invalid range
return
end

print("\n Given Number (a : ", a ,",b : ", b ,")")
#  Set all active bits of a given range
result = ((1 << (r2 - r1 + 1)) - 1) << ((r1 - 1))
#  Get copy result
result = (result & b) | a
#  Display calculated result
print("\n Result : ", result)
end

end

def main()
a = 37
b = 27
r1 = 3
r2 = 5
#  Test case a
#  a = 37 (100101)
#  b = 27 (011011)
#           ↓↓↓  (range r1 = 3, r2 = 5)
#  result (111101) = 61
#  Test case b
a = 37
b = 19
r1 = 2
r2 = 5
#  a = 37 (100101)
#  b = 19 (010011)
#           ↓↓↓↓ (range r1 = 2, r2 = 5)
#  result (110111) (55)
end

main()``````

#### Output

`````` Given Number (a : 37,b : 27)
Result : 61
Given Number (a : 37,b : 19)
Result : 55``````
``````/*
Scala program
Copy set bits in a range
*/
class BitManipulation
{
// Copy all active bits (B to A) of from given range
def copyBit(a: Int, b: Int, r1: Int, r2: Int): Unit = {
// Invalid range
if (r1 < 0 || r2 < 0 || r1 > 31 && r2 > 31)
{
return;
}
print("\n Given Number (a : " + a + ",b : " + b + ")");
// Set all active bits of a given range
var result: Int = ((1 << (r2 - r1 + 1)) - 1) << ((r1 - 1));
// Get copy result
result = (result & b) | a;
// Display calculated result
print("\n Result : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BitManipulation = new BitManipulation();
var a: Int = 37;
var b: Int = 27;
var r1: Int = 3;
var r2: Int = 5;
// Test case a
// a = 37 (100101)
// b = 27 (011011)
//          ↓↓↓  (range r1 = 3, r2 = 5)
// result (111101) = 61
// Test case b
a = 37;
b = 19;
r1 = 2;
r2 = 5;
// a = 37 (100101)
// b = 19 (010011)
//          ↓↓↓↓ (range r1 = 2, r2 = 5)
// result (110111) (55)
}
}``````

#### Output

`````` Given Number (a : 37,b : 27)
Result : 61
Given Number (a : 37,b : 19)
Result : 55``````
``````/*
Swift 4 program
Copy set bits in a range
*/
class BitManipulation
{
// Copy all active bits (B to A) of from given range
func copyBit(_ a: Int, _ b: Int, _ r1: Int, _ r2: Int)
{
// Invalid range
if (r1 < 0 || r2 < 0 || r1 > 31 && r2 > 31)
{
return;
}
print("\n Given Number (a : ", a ,",b : ", b ,")", terminator: "");
// Set all active bits of a given range
var result: Int = ((1 << (r2 - r1 + 1)) - 1) << ((r1 - 1));
// Get copy result
result = (result & b) | a;
// Display calculated result
print("\n Result : ", result, terminator: "");
}
}
func main()
{
var a: Int = 37;
var b: Int = 27;
var r1: Int = 3;
var r2: Int = 5;
// Test case a
// a = 37 (100101)
// b = 27 (011011)
//          ↓↓↓  (range r1 = 3, r2 = 5)
// result (111101) = 61
// Test case b
a = 37;
b = 19;
r1 = 2;
r2 = 5;
// a = 37 (100101)
// b = 19 (010011)
//          ↓↓↓↓ (range r1 = 2, r2 = 5)
// result (110111) (55)
}
main();``````

#### Output

`````` Given Number (a :  37 ,b :  27 )
Result :  61
Given Number (a :  37 ,b :  19 )
Result :  55``````
``````/*
Kotlin program
Copy set bits in a range
*/
class BitManipulation
{
// Copy all active bits (B to A) of from given range
fun copyBit(a: Int, b: Int, r1: Int, r2: Int): Unit
{
// Invalid range
if (r1 < 0 || r2 < 0 || r1 > 31 && r2 > 31)
{
return;
}
print("\n Given Number (a : " + a + ",b : " + b + ")");
// Set all active bits of a given range
var result: Int = ((1 shl(r2 - r1 + 1)) - 1) shl ((r1 - 1));
// Get copy result
result = (result and b) or a;
// Display calculated result
print("\n Result : " + result);
}
}
fun main(args: Array < String > ): Unit
{
var a: Int = 37;
var b: Int = 27;
var r1: Int = 3;
var r2: Int = 5;
// Test case a
// a = 37 (100101)
// b = 27 (011011)
//          ↓↓↓  (range r1 = 3, r2 = 5)
// result (111101) = 61
// Test case b
a = 37;
b = 19;
r1 = 2;
r2 = 5;
// a = 37 (100101)
// b = 19 (010011)
//          ↓↓↓↓ (range r1 = 2, r2 = 5)
// result (110111) (55)
}``````

#### Output

`````` Given Number (a : 37,b : 27)
Result : 61
Given Number (a : 37,b : 19)
Result : 55``````

## Time Complexity Analysis

The time complexity of this algorithm is constant O(1) because the operations involve simple bitwise shifts and logical AND/OR operations, which take constant time regardless of the input size. The range of possible inputs is limited (0 to 31), so the algorithm's performance does not depend on the input size.

## Output Explanation

The given code first executes the `copy_bit` function twice with different test cases and prints the results.

For test case `a = 37`, `b = 27`, `r1 = 3`, and `r2 = 5`:

• The function `copy_bit(37, 27, 3, 5)` is called.
• The binary representation of `37` is `100101`.
• The binary representation of `27` is `011011`.
• The active bits in the range `r1` to `r2` of `b` are `011`.
• After setting these bits in `a`, the modified `a` becomes `111101`, which is `61` in decimal.
• The function prints "Given Number (a : 37, b : 27)" and "Result : 61" as output.

For test case `a = 37`, `b = 19`, `r1 = 2`, and `r2 = 5`:

• The function `copy_bit(37, 19, 2, 5)` is called.
• The binary representation of `37` is `100101`.
• The binary representation of `19` is `010011`.
• The active bits in the range `r1` to `r2` of `b` are `1001`.
• After setting these bits in `a`, the modified `a` becomes `110111`, which is `55` in decimal.
• The function prints "Given Number (a : 37, b : 19)" and "Result : 55" as output.

Therefore, the program successfully copies set bits from the specified range of `b` to `a` and provides the correct output for both test cases.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post