Anni_housie Anni_housie - 18 days ago 6
C++ Question

swap bit i and j of an integer

Given an integer, swap the i-th and j-th bit.

I have tried solving this question myself. Do you guys think it is too "wordy" (long)?

int swap_bit(int num, int i, int j){
int a=(num>>i) & 1; //i-th bit
int b=(num>>j) & 1; //j-th bit

int mask1=~(1<<i); // create mask to clear i-th bit
int mask2=~(1<<j); // create mask to clear j-th bit

num=num & mask1 & mask2;
num=num | (a<<j);
num=num | (b<<i);
return num;
}

Answer

I always refer to https://graphics.stanford.edu/~seander/bithacks.html for anything bit-related.

Swapping individual bits with XOR

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

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

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.


For the special case where n = 1 the code reduces to:

unsigned int i, j; // positions of bit sequences to swap
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; // XOR temporary
r = b ^ ((x << i) | (x << j));
Comments