Programming Praxis

As before, we will work in C.

1) Compute the minimum (or maximum) of two integers without branching: We declare integers x and y to hold the two integers and integer r to hold the result. The obvious way to compute the minimum uses a branch:

int x, y, r;
r = (x y) ? x : y; // max(x,y)

But the problem specifies that we can’t use a branch, because branching can destroy performance on modern CPU architectures. Here is our solution

int x, y, r;
r = y ^ ((x ^ y) & -(x < y)); // min(x, y)
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

In the calculation of the minimum, -(x < y) is all 1’s if x < y and all 0’s otherwise. Thus the expression in the outer parentheses is x ^ y if x < y and all 0’s otherwise. Then the result is y ^ (x ^ y) = x if x < y and y ^ 0 = y otherwise. A similar discussion holds for the calculation of the maximum.

2) Determine if an integer is a power of two: We have two solutions:

unsigned int v;
bool f;
f = (v & (v - 1)) == 0;

If v is a power of two, a single bit will be set. Subtracting 1 unsets that bit and sets all trailing bits, so the and makes all the bits 0. That expression incorrectly recognizes 0 as a power of two, which is frequently okay, since v can never be zero; if it’s not okay, use this expression instead:

f = v && !(v & (v - 1));

3) Swap the values of two variables without using any extra space: Our first solution, using xor is famous; I remember being incredulous the first time I saw this trick:

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

We give an example using 8-bit integers. Assume a = 00100101 and b = 01010100. Then a ^ b = 01110001 is stored in a, b ^ a = 00100101 (using the new a) is stored in b, and a ^ b = 01010100 (using the new a and b) is stored in a, swapping the two variables.

This assumes a and b are different memory locations, and that both are integers. Our second solution uses addition and subtraction:

#define SWAP(a, b) (((a) -= (b)), ((b) += (a)), ((a) = (b) - (a)))

This also assumes the two variables are different memory locations, that both are unsigned integers, and is also subject to overflow, and it may be slower than the other solution but certainly won’t be faster, so you might want to ignore it.

You can run all these programs at http://programmingpraxis.codepad.org/lRQsixgC. The people that think up these hacks are seriously warped.

Pages: 1 2