Skip to main content

Find the sum of bit differences among all pairs

Swapping the values of variables is a common operation in programming. Typically, programmers use a temporary (fourth) variable to perform the swap. However, there are methods to perform variable swapping without using an additional variable. In this article, we will discuss a method to swap three variables using the XOR operation.

Problem Statement

The problem is to swap the values of three variables x, y, and z without using any extra variable. In other words, after the swap, x should contain the initial value of y, y should contain the initial value of z, and z should contain the initial value of x.

Explanation with Suitable Example

Let's take an example to understand the problem better: Suppose we have three variables:

int x = 10;
int y = 20;
int z = 30;

We want to swap their values such that:

x = 20;
y = 30;
z = 10;

Standard Pseudocode

The swap function can be implemented using XOR as follows:

function swapThreeVariables(x, y, z):
    x = x ^ y ^ z
    y = x ^ y ^ z
    z = x ^ y ^ z
    x = x ^ y ^ z
    return x, y, z

Algorithm Explanation

  1. We take the XOR of all three variables and store it in x. At this point, x will contain the combined value of x, y, and z.
  2. Then, we use the XOR operation to find the original values and store them in y and z. Since x now holds the combined value, XORing it with the current value of y gives us the original value of z, and XORing it with the current value of z gives us the original value of y.
  3. Finally, we again XOR the combined value (now stored in x) with the new values in y and z to obtain the original value of x.

Code Solution

Here given code implementation process.

// C program 
// Find the sum of bit differences among all pairs
#include <stdio.h>

// Display array elements
void display(int num[], int n)
{
	printf("\n Given number : ");
	for (int i = 0; i < n; ++i)
	{
		printf(" %d", num[i]);
	}
}
// Find sum of bit differences of all existing pair in given array
void pair_bit_diff(int num[], int n)
{
	display(num, n);
	// Work with 4 byte integer
	// 1 byte 8 bit so 4 byte 32 bit
	int bits = 32;
	// Use to collect result
	int result = 0;
	// Set bit counter
	int count = 0;
	// Execute loop through by 4 bytes
	for (int i = 0; i < bits; ++i)
	{
		// Execute loop through by size of num
		for (int j = 0; j < n; ++j)
		{
			if ((1 << i) & num[j])
			{
				// When ith bit is active
				count++;
			}
		}
		// Add different bits result
		// Here count indicates active bits
		// n is total number of bits
		result += (count *(n - count)) *2;
		// Reset bit counter
		count = 0;
	}
	// Display calculated result
	printf("\n Bit Different : %d\n", result);
}
int main(int argc, char
	const *argv[])
{
	int num[] = {
		3 , 8 , 1 , 2
	};
	// Get the number of elements
	int n = sizeof(num) / sizeof(num[0]);
	// Test
	pair_bit_diff(num, n);
	return 0;
}

Output

 Given number :  3 8 1 2
 Bit Different : 22
/*
  Java program
  Find the sum of bit differences among all pairs
*/
public class Difference
{
	// Display array elements
	public void display(int[] num, int n)
	{
		System.out.print("\n Given number  : ");
		for (int i = 0; i < n; ++i)
		{
			System.out.print("  " + num[i]);
		}
	}
	// Find sum of bit differences of all existing pair in given array
	public void pairBitDifference(int[] num, int n)
	{
		display(num, n);
		// Work with 4 byte integer
		// 1 byte 8 bit so 4 byte 32 bit
		int bits = 32;
		// Use to collect result
		int result = 0;
		// Set bit counter
		int count = 0;
		// Execute loop through by 4 bytes
		for (int i = 0; i < bits; ++i)
		{
			// Execute loop through by size of num
			for (int j = 0; j < n; ++j)
			{
				if (((1 << i) & num[j]) != 0)
				{
					// When ith bit is active
					count++;
				}
			}
			// Add different bits result
			// Here count indicates active bits
			// n is total number of bits
			result += (count * (n - count)) * 2;
			// Reset bit counter
			count = 0;
		}
		// Display calculated result
		System.out.print("\n Bit Different : " + result + "\n");
	}
	public static void main(String[] args)
	{
		Difference task = new Difference();
		int[] num = {
			3 , 8 , 1 , 2
		};
		// Get the number of elements
		int n = num.length;
		// Test
		task.pairBitDifference(num, n);
	}
}

Output

 Given number  :   3  8  1  2
 Bit Different : 22
// Include header file
#include <iostream>

using namespace std;
/*
  C++ program
  Find the sum of bit differences among all pairs
*/
class Difference
{
	public:
		// Display array elements
		void display(int num[], int n)
		{
			cout << "\n Given number  : ";
			for (int i = 0; i < n; ++i)
			{
				cout << "  " << num[i];
			}
		}
	// Find sum of bit differences of all existing pair in given array
	void pairBitDifference(int num[], int n)
	{
		this->display(num, n);
		// Work with 4 byte integer
		// 1 byte 8 bit so 4 byte 32 bit
		int bits = 32;
		// Use to collect result
		int result = 0;
		// Set bit counter
		int count = 0;
		// Execute loop through by 4 bytes
		for (int i = 0; i < bits; ++i)
		{
			// Execute loop through by size of num
			for (int j = 0; j < n; ++j)
			{
				if (((1 << i) &num[j]) != 0)
				{
					// When ith bit is active
					count++;
				}
			}
			// Add different bits result
			// Here count indicates active bits
			// n is total number of bits
			result += (count *(n - count)) *2;
			// Reset bit counter
			count = 0;
		}
		// Display calculated result
		cout << "\n Bit Different : " << result << "\n";
	}
};
int main()
{
	Difference task = Difference();
	int num[] = {
		3 , 8 , 1 , 2
	};
	// Get the number of elements
	int n = sizeof(num) / sizeof(num[0]);
	// Test
	task.pairBitDifference(num, n);
	return 0;
}

Output

 Given number  :   3  8  1  2
 Bit Different : 22
// Include namespace system
using System;
/*
  C# program
  Find the sum of bit differences among all pairs
*/
public class Difference
{
	// Display array elements
	public void display(int[] num, int n)
	{
		Console.Write("\n Given number  : ");
		for (int i = 0; i < n; ++i)
		{
			Console.Write("  " + num[i]);
		}
	}
	// Find sum of bit differences of all existing pair in given array
	public void pairBitDifference(int[] num, int n)
	{
		display(num, n);
		// Work with 4 byte integer
		// 1 byte 8 bit so 4 byte 32 bit
		int bits = 32;
		// Use to collect result
		int result = 0;
		// Set bit counter
		int count = 0;
		// Execute loop through by 4 bytes
		for (int i = 0; i < bits; ++i)
		{
			// Execute loop through by size of num
			for (int j = 0; j < n; ++j)
			{
				if (((1 << i) & num[j]) != 0)
				{
					// When ith bit is active
					count++;
				}
			}
			// Add different bits result
			// Here count indicates active bits
			// n is total number of bits
			result += (count * (n - count)) * 2;
			// Reset bit counter
			count = 0;
		}
		// Display calculated result
		Console.Write("\n Bit Different : " + result + "\n");
	}
	public static void Main(String[] args)
	{
		Difference task = new Difference();
		int[] num = {
			3 , 8 , 1 , 2
		};
		// Get the number of elements
		int n = num.Length;
		// Test
		task.pairBitDifference(num, n);
	}
}

Output

 Given number  :   3  8  1  2
 Bit Different : 22
<?php
/*
  Php program
  Find the sum of bit differences among all pairs
*/
class Difference
{
	// Display array elements
	public	function display( & $num, $n)
	{
		echo "\n Given number  : ";
		for ($i = 0; $i < $n; ++$i)
		{
			echo "  ". $num[$i];
		}
	}
	// Find sum of bit differences of all existing pair in given array
	public	function pairBitDifference( & $num, $n)
	{
		$this->display($num, $n);
		// Work with 4 byte integer
		// 1 byte 8 bit so 4 byte 32 bit
		$bits = 32;
		// Use to collect result
		$result = 0;
		// Set bit counter
		$count = 0;
		// Execute loop through by 4 bytes
		for ($i = 0; $i < $bits; ++$i)
		{
			// Execute loop through by size of num
			for ($j = 0; $j < $n; ++$j)
			{
				if (((1 << $i) & $num[$j]) != 0)
				{
					// When ith bit is active
					$count++;
				}
			}
			// Add different bits result
			// Here count indicates active bits
			// n is total number of bits
			$result += ($count * ($n - $count)) * 2;
			// Reset bit counter
			$count = 0;
		}
		// Display calculated result
		echo "\n Bit Different : ". $result ."\n";
	}
}

function main()
{
	$task = new Difference();
	$num = array(3, 8, 1, 2);
	// Get the number of elements
	$n = count($num);
	// Test
	$task->pairBitDifference($num, $n);
}
main();

Output

 Given number  :   3  8  1  2
 Bit Different : 22
/*
  Node Js program
  Find the sum of bit differences among all pairs
*/
class Difference
{
	// Display array elements
	display(num, n)
	{
		process.stdout.write("\n Given number  : ");
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write("  " + num[i]);
		}
	}
	// Find sum of bit differences of all existing pair in given array
	pairBitDifference(num, n)
	{
		this.display(num, n);
		// Work with 4 byte integer
		// 1 byte 8 bit so 4 byte 32 bit
		var bits = 32;
		// Use to collect result
		var result = 0;
		// Set bit counter
		var count = 0;
		// Execute loop through by 4 bytes
		for (var i = 0; i < bits; ++i)
		{
			// Execute loop through by size of num
			for (var j = 0; j < n; ++j)
			{
				if (((1 << i) & num[j]) != 0)
				{
					// When ith bit is active
					count++;
				}
			}
			// Add different bits result
			// Here count indicates active bits
			// n is total number of bits
			result += (count * (n - count)) * 2;
			// Reset bit counter
			count = 0;
		}
		// Display calculated result
		process.stdout.write("\n Bit Different : " + result + "\n");
	}
}

function main()
{
	var task = new Difference();
	var num = [3, 8, 1, 2];
	// Get the number of elements
	var n = num.length;
	// Test
	task.pairBitDifference(num, n);
}
main();

Output

 Given number  :   3  8  1  2
 Bit Different : 22
#   Python 3 program
#   Find the sum of bit differences among all pairs

class Difference :
	#  Display list elements
	def display(self, num, n) :
		print("\n Given number  : ", end = "")
		i = 0
		while (i < n) :
			print("  ", num[i], end = "")
			i += 1
		
	
	#  Find sum of bit differences of all existing pair in given list
	def pairBitDifference(self, num, n) :
		self.display(num, n)
		#  Work with 4 byte integer
		#  1 byte 8 bit so 4 byte 32 bit
		bits = 32
		#  Use to collect result
		result = 0
		#  Set bit counter
		count = 0
		#  Execute loop through by 4 bytes
		i = 0
		while (i < bits) :
			#  Execute loop through by size of num
			j = 0
			while (j < n) :
				if (((1 << i) & num[j]) != 0) :
					#  When ith bit is active
					count += 1
				
				j += 1
			
			#  Add different bits result
			#  Here count indicates active bits
			#  n is total number of bits
			result += (count * (n - count)) * 2
			#  Reset bit counter
			count = 0
			i += 1
		
		#  Display calculated result
		print("\n Bit Different : ", result )
	

def main() :
	task = Difference()
	num = [3, 8, 1, 2]
	#  Get the number of elements
	n = len(num)
	#  Test
	task.pairBitDifference(num, n)

if __name__ == "__main__": main()

Output

 Given number  :    3   8   1   2
 Bit Different :  22
#   Ruby program
#   Find the sum of bit differences among all pairs

class Difference 
	#  Display array elements
	def display(num, n) 
		print("\n Given number  : ")
		i = 0
		while (i < n) 
			print("  ", num[i])
			i += 1
		end

	end

	#  Find sum of bit differences of all existing pair in given array
	def pairBitDifference(num, n) 
		self.display(num, n)
		#  Work with 4 byte integer
		#  1 byte 8 bit so 4 byte 32 bit
		bits = 32
		#  Use to collect result
		result = 0
		#  Set bit counter
		count = 0
		#  Execute loop through by 4 bytes
		i = 0
		while (i < bits) 
			#  Execute loop through by size of num
			j = 0
			while (j < n) 
				if (((1 << i) & num[j]) != 0) 
					#  When ith bit is active
					count += 1
				end

				j += 1
			end

			#  Add different bits result
			#  Here count indicates active bits
			#  n is total number of bits
			result += (count * (n - count)) * 2
			#  Reset bit counter
			count = 0
			i += 1
		end

		#  Display calculated result
		print("\n Bit Different : ", result ,"\n")
	end

end

def main() 
	task = Difference.new()
	num = [3, 8, 1, 2]
	#  Get the number of elements
	n = num.length
	#  Test
	task.pairBitDifference(num, n)
end

main()

Output

 Given number  :   3  8  1  2
 Bit Different : 22

/*
  Scala program
  Find the sum of bit differences among all pairs
*/
class Difference
{
	// Display array elements
	def display(num: Array[Int], n: Int): Unit = {
		print("\n Given number  : ");
		var i: Int = 0;
		while (i < n)
		{
			print("  " + num(i));
			i += 1;
		}
	}
	// Find sum of bit differences of all existing pair in given array
	def pairBitDifference(num: Array[Int], n: Int): Unit = {
		this.display(num, n);
		// Work with 4 byte integer
		// 1 byte 8 bit so 4 byte 32 bit
		var bits: Int = 32;
		// Use to collect result
		var result: Int = 0;
		// Set bit counter
		var count: Int = 0;
		// Execute loop through by 4 bytes
		var i: Int = 0;
		while (i < bits)
		{
			// Execute loop through by size of num
			var j: Int = 0;
			while (j < n)
			{
				if (((1 << i) & num(j)) != 0)
				{
					// When ith bit is active
					count += 1;
				}
				j += 1;
			}
			// Add different bits result
			// Here count indicates active bits
			// n is total number of bits
			result += (count * (n - count)) * 2;
			// Reset bit counter
			count = 0;
			i += 1;
		}
		// Display calculated result
		print("\n Bit Different : " + result + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Difference = new Difference();
		var num: Array[Int] = Array(3, 8, 1, 2);
		// Get the number of elements
		var n: Int = num.length;
		// Test
		task.pairBitDifference(num, n);
	}
}

Output

 Given number  :   3  8  1  2
 Bit Different : 22
/*
  Swift 4 program
  Find the sum of bit differences among all pairs
*/
class Difference
{
	// Display array elements
	func display(_ num: [Int], _ n: Int)
	{
		print("\n Given number  : ", terminator: "");
		var i: Int = 0;
		while (i < n)
		{
			print("  ", num[i], terminator: "");
			i += 1;
		}
	}
	// Find sum of bit differences of all existing pair in given array
	func pairBitDifference(_ num: [Int], _ n: Int)
	{
		self.display(num, n);
		// Work with 4 byte integer
		// 1 byte 8 bit so 4 byte 32 bit
		let bits: Int = 32;
		// Use to collect result
		var result: Int = 0;
		// Set bit counter
		var count: Int = 0;
		// Execute loop through by 4 bytes
		var i: Int = 0;
		while (i < bits)
		{
			// Execute loop through by size of num
			var j: Int = 0;
			while (j < n)
			{
				if (((1 << i) & num[j])  != 0)
				{
					// When ith bit is active
					count += 1;
				}
				j += 1;
			}
			// Add different bits result
			// Here count indicates active bits
			// n is total number of bits
			result += (count * (n - count)) * 2;
			// Reset bit counter
			count = 0;
			i += 1;
		}
		// Display calculated result
		print("\n Bit Different : ", result );
	}
}
func main()
{
	let task: Difference = Difference();
	let num: [Int] = [3, 8, 1, 2];
	// Get the number of elements
	let n: Int = num.count;
	// Test
	task.pairBitDifference(num, n);
}
main();

Output

 Given number  :    3   8   1   2
 Bit Different :  22
/*
  Kotlin program
  Find the sum of bit differences among all pairs
*/
class Difference
{
	// Display array elements
	fun display(num: Array < Int > , n: Int): Unit
	{
		print("\n Given number  : ");
		var i: Int = 0;
		while (i < n)
		{
			print("  " + num[i]);
			i += 1;
		}
	}
	// Find sum of bit differences of all existing pair in given array
	fun pairBitDifference(num: Array < Int > , n: Int): Unit
	{
		this.display(num, n);
		// Work with 4 byte integer
		// 1 byte 8 bit so 4 byte 32 bit
		var bits: Int = 32;
		// Use to collect result
		var result: Int = 0;
		// Set bit counter
		var count: Int = 0;
		// Execute loop through by 4 bytes
		var i: Int = 0;
		while (i < bits)
		{
			// Execute loop through by size of num
			var j: Int = 0;
			while (j < n)
			{
				if (((1 shl i) and num[j]) != 0)
				{
					// When ith bit is active
					count += 1;
				}
				j += 1;
			}
			// Add different bits result
			// Here count indicates active bits
			// n is total number of bits
			result += (count * (n - count)) * 2;
			// Reset bit counter
			count = 0;
			i += 1;
		}
		// Display calculated result
		print("\n Bit Different : " + result + "\n");
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Difference = Difference();
	var num: Array < Int > = arrayOf(3, 8, 1, 2);
	// Get the number of elements
	var n: Int = num.count();
	// Test
	task.pairBitDifference(num, n);
}

Output

 Given number  :   3  8  1  2
 Bit Different : 22

Time Complexity

The time complexity of the swap function is O(1) because the XOR operation takes constant time, irrespective of the values of the variables involved.

Last updated on by Kalkicode




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