Saturday, January 21, 2012

Swap Individual Bits

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

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