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
- We take the XOR of all three variables and store it in
x
. At this point,x
will contain the combined value ofx
,y
, andz
. - Then, we use the XOR operation to find the original values and store them in
y
andz
. Sincex
now holds the combined value, XORing it with the current value ofy
gives us the original value ofz
, and XORing it with the current value ofz
gives us the original value ofy
. - Finally, we again XOR the combined value (now stored in
x
) with the new values iny
andz
to obtain the original value ofx
.
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.
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