Swap individual bits at a given position in an integer

Given an integer, swap consecutive b bits starting from the given positions in a binary representation of an integer. The bits to be swapped should not overlap with each other.

For example,

Input:

n = 15 (15 in binary is 00001111)
p = 2, q = 5 (3rd and 6th bit from the right)
b = 2 (Total number of consecutive bits in each sequence)

Output: 99

(99 in binary is 01100011)

Practice this problem

The idea is to store the result of XORing the pairs of bit values we want to swap in a variable x, and then the bits are set to the result of themselves XORed with x. The code goes as:

// isolate the bits to be swapped and take their XOR
x = ((n >> p) ^ (n >> q)) & ((1 << b) – 1)

// replace the bits to be swapped with the XOR bits and take its XOR with n
result = n ^ ((x << p) | (x << q))

Note that the result is undefined if the sequences overlap.

For example, consider n = 15, p = 2, q = 5 (3rd and 6th bit from the right) and number of consecutive bits in each sequence b = 2.

00001111                (n = 15)

00000011    ^           (n >> p)
00000000                (n >> q)
~~~~~~~~
00000011                ((n >> p) ^ (n >> q))

00000011    &           ((n >> p) ^ (n >> q))
00000011                ((1 << b) – 1)
~~~~~~~~
00000011                x

00001100    |           (x << p)
01100000                (x << q)
~~~~~~~~
01101100                ((x << p) | (x << q))

00001111    ^           (n = 15)
01101100                (n ^ ((x << p) | (x << q)))
~~~~~~~~
01100011

Following is the C++, Java, and Python implementation of the idea:

C++

#include <iostream>

#include <bitset>

using namespace std;

// Function to swap b–bits starting from position `p` and `q` in an integer `n`

int swap(int n, int p, int q, int b)

{

// take XOR of bits to be swapped

int x = ((n >> p) ^ (n >> q));

// only consider the last b–bits of `x`

x = x & ((1 << b) - 1);

// replace the bits to be swapped with the XORed bits

// and take its XOR with `n`

return n ^ ((x << p) | (x << q));

}

int main()

{

int n = 15;

int p = 2, q = 5; // 3rd and 6th bit from the right

int b = 2; // total number of consecutive bits in each sequence

cout << n << " in binary is " << bitset<8>(n) << endl;

n = swap (n, p, q, b);

cout << n << " in binary is " << bitset<8>(n) << endl;

return 0;

}

Download Run Code

Output:

15 in binary is 00001111
99 in binary is 01100011

Java

class Main

{

public static String toBinaryString(int n)

{

return String.format("%8s", Integer.toBinaryString(n))

.replaceAll(" ", "0");

}

// Function to swap b–bits starting from position `p` and `q` in an integer `n`

public static int swap(int n, int p, int q, int b)

{

// take XOR of bits to be swapped

int x = ((n >> p) ^ (n >> q));

// only consider the last b–bits of `x`

x = x & ((1 << b) - 1);

// replace the bits to be swapped with the XOR bits

// and take its XOR with `n`

return n ^ ((x << p) | (x << q));

}

public static void main(String[] args)

{

int n = 15;

int p = 2, q = 5; // 3rd and 6th bit from the right

int b = 2; // total number of consecutive bits in each sequence

System.out.println(n + " in binary is " + toBinaryString(n));

n = swap (n, p, q, b);

System.out.println(n + " in binary is " + toBinaryString(n));

}

Download Run Code

Output:

15 in binary is 00001111
99 in binary is 01100011

Python

# Function to swap b–bits starting from position `p` and `q` in an integer `n`

def swap(n, p, q, b):

# take XOR of bits to be swapped

x = ((n >> p) ^ (n >> q))

# only consider the last b–bits of `x`

x = x & ((1 << b) - 1)

# replace the bits to be swapped with the XOR bits

# and take its XOR with `n`

return n ^ ((x << p) | (x << q))

if __name__ == '__main__':

n = 15

# 3rd and 6th bit from the right

p = 2

q = 5

# total number of consecutive bits in each sequence

b = 2

print(f'{n} in binary is {bin(n)}')

n = swap(n, p, q, b)

print(f'{n} in binary is {bin(n)}')

Download Run Code

Output:

15 in binary is 0b1111
99 in binary is 0b1100011

References: https://graphics.stanford.edu/~seander/bithacks.html#SwappingBitsXOR

Swap individual bits at a given position in an integer

C++

Java

Python

Share this: