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
.
- The bits to be copied from
b
are011
(range from position 3 to 5). - Now, we need to set these bits in
a
at positions 3 to 5. - The modified
a
will be111101
(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
- Check if the input ranges
r1
andr2
are valid (non-negative and less than or equal to 31). If not, return an error indicating an invalid range. - Calculate a bitmask
result
to set all the active bits from the ranger1
tor2
. 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 byr1
positions to place it at the correct range ina
. - Perform a bitwise AND operation between the bitmask
result
andb
to extract the set bits fromb
within the specified range. - Perform a bitwise OR operation between the extracted bits from step 3 and
a
to set the bits ina
as required. - 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)
{
BitManipulation task = new BitManipulation();
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
task.copyBit(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)
task.copyBit(a, b, r1, r2);
}
}
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()
{
BitManipulation task = BitManipulation();
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
task.copyBit(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)
task.copyBit(a, b, r1, r2);
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)
{
BitManipulation task = new BitManipulation();
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
task.copyBit(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)
task.copyBit(a, b, r1, r2);
}
}
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()
{
$task = new BitManipulation();
$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
$task->copyBit($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)
$task->copyBit($a, $b, $r1, $r2);
}
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 task = new BitManipulation();
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
task.copyBit(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)
task.copyBit(a, b, r1, r2);
}
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() :
task = BitManipulation()
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
task.copyBit(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)
task.copyBit(a, b, r1, r2)
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()
task = BitManipulation.new()
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
task.copyBit(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)
task.copyBit(a, b, r1, r2)
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
task.copyBit(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)
task.copyBit(a, b, r1, r2);
}
}
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()
{
let task: BitManipulation = 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
task.copyBit(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)
task.copyBit(a, b, r1, r2);
}
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 task: BitManipulation = 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
task.copyBit(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)
task.copyBit(a, b, r1, r2);
}
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
is100101
. - The binary representation of
27
is011011
. - The active bits in the range
r1
tor2
ofb
are011
. - After setting these bits in
a
, the modifieda
becomes111101
, which is61
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
is100101
. - The binary representation of
19
is010011
. - The active bits in the range
r1
tor2
ofb
are1001
. - After setting these bits in
a
, the modifieda
becomes110111
, which is55
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.
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.
New Comment