Given an 32-bit integer X, swap the i-th and j-th bit. And also swap a bit range between two numbers
We can swap individual bits using XOR technique.
swap(int n,int i,int j)
{
if( (n & 1<<i)>>i ^ (n & (1<<j))>>j) ) // if bits i and j are different
{
n^= 1<<i;
n^= 1<<j;
}
return n;
}
Swapping ranges of bits
As an example of swapping ranges of bits suppose we have have b = 00101111 (expressed in binary) and we want to swap the n = 3 consecutive bits starting at i = 1 (the second bit from the right) with the 3 consecutive bits starting at j = 5; the result would be r = 11100011 (binary).
We can swap individual bits using XOR technique.
swap(int n,int i,int j)
{
if( (n & 1<<i)>>i ^ (n & (1<<j))>>j) ) // if bits i and j are different
{
n^= 1<<i;
n^= 1<<j;
}
return n;
}
Swapping ranges of bits
As an example of swapping ranges of bits suppose we have have b = 00101111 (expressed in binary) and we want to swap the n = 3 consecutive bits starting at i = 1 (the second bit from the right) with the 3 consecutive bits starting at j = 5; the result would be r = 11100011 (binary).
unsigned int i, j; // positions of bit sequences to swap unsigned int n; // number of consecutive bits in each sequence unsigned int b; // bits to swap reside in b unsigned int r; // bit-swapped result goes here unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // XOR temporary r = b ^ ((x << i) | (x << j));
This method of swapping is similar to the general purpose XOR swap trick, but intended for operating on individual bits. The variable x stores the result of XORing the pairs of bit values we want to swap, and then the bits are set to the result of themselves XORed with x. Of course, the result is undefined if the sequences overlap.
Useful Links:
http://en.wikipedia.org/wiki/XOR_swap_algorithm
No comments:
Post a Comment