I've been looking at some of these books with fun interview problems. One has a question where one is supposed to write code to flip two bits in a 64-bit integer given the indices of the two bits. After playing around with this for a while I came up with the following code, which is faster than the solution given in the textbook, since it doesn't have any branches:
uint64_t swapbits(uint64_t n, size_t i, size_t j)
{
// extract ith and jth bit
uint64_t bi = ((uint64_t) 0x1 << i) & n;
uint64_t bj = ((uint64_t) 0x1 << j) & n;
// clear ith and jth bit in n
n ^= bi | bj;
n ^= (bi >> i) << j;
n ^= (bj >> j) << i;
return n;
}
My question is essentially the following: Is there an even faster way of doing this?
EDIT: Here's the other implementation as reference:
uint64_t swapbits(uint64_t x, size_t i, size_t j)
{
if(((x >> i) & 1) != ((x >> j) & 1)) {
x ^= (1L << i) | (1L << j);
}
return x;
}
With compiler optimizations the latter is around 35% slower on a Core i7 4770. As I said in the comments, I'm interested in whether there are any interesting tricks for doing this very efficiently. I've seen some extremely clever bit fiddling tricks that can do something that looks fairly complicated in just a few instructions.
Here's a solution which uses only 8 operations. Note that this works even when i == j.
uint64_t swapbits(uint64_t n, size_t i, size_t j)
{
uint64_t x = ((n >> i) ^ (n >> j)) & 1; // x = 1 bit "toggle" flag
return n ^ ((x << i) | (x << j)); // apply toggle to bits i and j
}
Explanation: x is equal to 1 only if the original bits at indices i and j are different (10 or 01), and therefore need to be toggled. Otherwise it's zero and the bits are to remain unchanged (00 or 11). We then apply this toggle bit to the original bits (i.e. XOR it with the original bits) to get the required result.