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)
    {
        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 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.

New Comment





Categories
Relative Post