Table Bitpacking to avoid lookup tables and switches / Reversing Nibbles and Bytes

Problem: Write a c++ function to reverse a nibble (a nibble is 4 bits); you may assume the nibble 'n' is being passed as an unsigned byte and is guaranteed to already be within the valid 0~15 range (so you don't have to have AND it with 15 or have assertions).

A straight-forward solution for this problem would something this:

u8 rev_nibble(u8 n) {
    u8 ret = 0;
    if (n&1) ret |= 8;
    if (n&2) ret |= 4;
    if (n&4) ret |= 2;
    if (n&8) ret |= 1;
    return ret;
}

A cooler solution is:

u8 rev_nibble(u8 n) {
    return ((n & 1)<<3) | ((n & 2)<<1) | ((n & 4)>>1) | ((n & 8)>>3);
}

Both the above solutions however consist of multiple instructions to accomplish such a simple thing, better solutions might use either a switch or a table:

u8 rev_nibble(u8 n) {
    static const u8 ret[16] = { 0x0,0x8,0x4,0xc,0x2,0xa,0x6,0xe,
                                0x1,0x9,0x5,0xd,0x3,0xb,0x7,0xf };
    return ret[n];
}

Now this last solution uses a trick I came up with (although I'm sure others have to), which I call "Table Bitpacking".

Instead of using a table to store the return values, notice that all return values only take up 4 bits (a nibble), and there's 16 of them, so in total you only need 64bits of data for the table. So we can just use a 64bit immediate value for the table, and shift out the result instead!

u8 rev_nibble(u8 n) {
    return (0xf7b3d591e6a2c480ull >> (n*4)) & 15;
}

Table bitpacking is cool because it can be used for many different permutations of tables; as long as the bits_per_choice * number_of_choices <= available_word_bits;
On 64bit platforms using 64bit tables should be fine, on 32bit platforms you'd want to stick to 32bit tables since 64bit shifts can be expensive.

Whether or not table bitpacking ends up being faster than the normal lookup table depends on the instruction set and the specific circumstances. But IMO its worth knowing the trick for possible future optimizations.

Now using our above function, we can do another common problem:
Problem: Reverse a byte!

Now that we know how to reverse a nibble, reversing a byte should be simple if we use the already existing rev_nibble function:

u8 rev_byte(u8 n) {
    return (rev_nibble(n & 15) << 4) | rev_nibble(n>>4);
}

Note: There are plenty of other ways to reverse a byte, perhaps the fastest is generally a 256 entry lookup-table for each byte permutation (now that table would be 256*256 bits, so too large to use the Table Bitpacking trick on current machines).

Edit:
Just thought I'd throw in one more cool way to reverse a nibble:

u8 rev_nibble(u8 n) {
    return "aiemckgobjfndlhp"[n] - 'a';
}

Bitwise Set-Bit (#2)

In a past article, I've shown some ways to do this. This time I'll show you another way to do it that I just came up with.

The problem:
Return 1 if a 32bit integer is non-zero, else return 0. The return-type should be a 32bit integer.

The Typical Solution:

s32 setBit(s32 x) {
    return x ? 1 : 0;
}

The Cooler Solution:

s32 setBit(s32 x) {
    return !!x; // Forces it to a bool which is 1 or 0
}

The Bitwise Solution:

s32 setBit(s32 x) {
    return (u32)(x | -x) >> 31;
}

The last one works because any non-zero integer will have its sign bit set either when negated or normally (if its already negative). The only number that won't have its sign bit set after ORing these results is 0. So we just logically-shift right by 31 to get a 1 or 0 value, which is what we wanted :D

Note 1: The bitwise trick in this case is not preferred, instead you should use the 'typical' or 'cool' solution, since the compiler will be able to optimize it better for the given architecture. On x86 there is a SETcc instruction which can be used which is likely faster than doing the bitwise trick since its less operations. This trick may still be useful to know though in-case you're doing asm or compiler work with some architecture that doesn't have a SETcc-like instruction (and you wish to avoid jumps). Although the method from my past article might be more helpful in this case.

Note 2: There is actually a number which has its sign bit set both normally and on negation, and that's the minimum-negative integer. With 32bit integers this number is -2147483648 (i.e. 0x80000000) (so with 32bit integers: 0x80000000 == -0x80000000).
Using this knowledge, we now learned another neat trick. You can detect the minimum negative integer by doing: bool isMinNeg = x == -x; // x can be an int type of any size

-1 or 1 bitwise trick

Been a while since my last update, and been a long time since my last bitwise trick.

The Problem:
If you have a 32bit signed integer, return -1 if the number is negative, and return 1 if the number is positive (or 0).

The Typical Solution:

s32 sign(s32 x) {
    return x < 0 ? -1 : 1;
}

The Bitwise Solution:

s32 sign(s32 x) {
    return (x>>31)|1;
}

How does it work?
Well (x>>31) does a signed shift with the sign bit, which will return either -1 if the sign bit was set (because -1 in binary is all 1's), or 0 if the sign bit wasn't set.
But we want to return 1 when its positive; so what we do is OR the result with 1. (-1 | 1) == -1, and (0 | 1) == 1.
So we get the result we wanted without needing a branch, and only using 2 very fast bitwise operations :D

Checking if a Float is a Power of 2

Last article I showed bitwise ways to check if integers are powers of 2, for completeness I'll show bitwise ways to check if floats are powers of 2.

For floating point numbers, remember that they're represented in the form |S*1|E*8|M*23|.
S = Sign Bit (1-bit)
E = Exponent (8-bits)
M = Mantissa (23-bits)

Check out the IEEE-754 standard for more info:
http://en.wikipedia.org/wiki/IEEE_754-1985

The exponent is actually used to compute powers of 2, which is then multiplied by the mantissa, which has an implicitly hidden '1.' in front of it.

So when we're checking if a float is a power of two, all we have to do is check if the mantissa is 0, and the exponent is non-zero (when the exponent is zero, the result is zero when the mantissa is also zero, or a denormal value when the mantissa is non-zero, so we don't want to consider these as powers of two).

The code ends up looking like this:

typedef unsigned __int32 u32;

bool isPow2(float f) {
    u32& i = (u32&)f;
    u32  e = (i>>23) & 0xff;
    u32  m =  i & 0x7fffff;
    return !m && e;
}

This however will end up counting negative-exponent powers of 2 (such as 2^-1 = 0.5), if this is not desirable, then we can modify the code to only count non-negative exponents (2^0 = 1, 2^1 = 2,...)

The modified code looks like this:

bool isPow2(float f) {
    u32& i = (u32&)f;
    u32  e = (i>>23) & 0xff;
    u32  m =  i & 0x7fffff;
    return !m && e >= 127;
}

One last thing, both these versions will also consider negative powers of two (such as -4, -2, -1) to be powers of two.
If this is also undesirable, then we just need to check the Sign-bit of the float to determine if its negative, and if it is, then we will return false.

This last function returns true if the float is a positive power of two with a positive exponent (1, 2, 4, 8, 16...).

bool isPow2(float f) {
    u32& i = (u32&)f;
    u32  s =  i>>31;
    u32  e = (i>>23) & 0xff;
    u32  m =  i & 0x7fffff;
    return !s && !m && e >= 127;
}

Checking if an Integer is a Power of 2

There are a few ways to check if an integer is a power of 2; some better than others.

One crucial thing to notice for power-of-two integers, is that in their binary representation, they only have 1 bit set.

0001 = 1
0010 = 2
0100 = 4
1000 = 8
... and so on...

So one approach we can do to check if an integer is a power of two, is to just loop through the bits, and check if only 1 bit is set.

bool isPow2(uint n) {
    const uint len = sizeof(uint)*8; // 32 for 4-byte integers
    uint count = 0;
    for(uint i = 0; i < len; i++) {
        count += n & 1;
        n >>= 1;
    }
    return count == 1;
}

Now the above approach is pretty obvious and simple; but its not that nice considering we have to loop for every bit (32 times for 4-byte integers).


There's a popular bitwise trick for determining if an integer is a power of 2, and it looks like this:

bool isPow2(uint n) {
    return (n & (n-1)) == 0;
}

Now this is a lot nicer than our loop version. Instead of looping 32 times, we do just a few bitwise calculations.

I was playing around with bitwise operations earlier today, and I discovered another bitwise method for checking powers of 2.

bool isPow2(uint n) {
    return (n & -n) == n;
}

I was really excited because I found this one out on my own, and I thought I had discovered it. However I did a google search on it, and I found out that this trick is already known :(

The nice thing about this second bitwise version, compared to the more popular version above it, is that its a lot simpler to remember IMO. Speed-wise, they're both around the same, I suppose it depends on your target architecture on which one is actually fastest, but in practical purposes it probably doesn't matter which one you use.

Note:
Its important to mention that both of the bitwise methods mentioned above, will incorrectly treat zero as a power of two.
To fix this behavior you can modify the functions like so:

bool isPow2(uint n) {
    return n && ((n & (n-1)) == 0);
}

and...

bool isPow2(uint n) {
    return n && ((n & -n) == n);
}

Sadly this adds an extra conditional to our fast bitwise methods, however it still ends up being a lot nicer (and faster) than our initial loop version.

Max/Min Values for Signed and Unsigned Ints

There are a variety of ways you can assign the max/min values to a signed/unsigned integer.

A very professional looking way is using the numeric_limits class like so:

#include <limits>

int main() {
    int x = numeric_limits<int>::max();
    int y = numeric_limits<int>::min();
    return 0;
}

But there are many other ways you can do this; and they all take a lot less typing than using numeric_limits, and you don't have to include any extra headers...

Lets first take a look at max/min integer values for different variables (in hexadecimal representation because its easier to memorize):

// u8, u16, u32... mean unsigned int of 8, 16, and 32 bits respectively
// s8, s16, s32... mean   signed int of 8, 16, and 32 bits respectively
----------------------------------
| type | max        | min        |
----------------------------------
| u8   | 0xff       | 0x0        |
| u16  | 0xffff     | 0x0        |
| u32  | 0xffffffff | 0x0        |
----------------------------------
| s8   | 0x7f       | 0x80       |
| s16  | 0x7fff     | 0x8000     |
| s32  | 0x7fffffff | 0x80000000 |
----------------------------------

The table is pretty easy to memorize. Essentially, for unsigned ints, the max value is always a bunch of f's in hexadecimal, and the min-value is always 0.
For signed ints, the max value is always 0x7f, followed by a bunch of f's.
And lastly the min value for signed ints is always 0x80, followed by a bunch of 0's.


One thing to notice is the bitwise representation for "-1" always has all-bits set.
That means that for a 32bit integer, "-1" is "0xffffffff", which is the max value for an unsigned integer.

This means that for unsigned integers, we can declare int max/min like this:

int main() {
    unsigned int x = -1u; // Unsigned int max
    unsigned int y = 0;   // Unsigned int min
    return 0;
}

In c++, you can put the suffix "u" at the end of an int literal to mean its unsigned. So what that code is doing, is treating the value "-1" as an unsigned int, which means its assigning 0xffffffff to the variable 'x'.

Here's the thing, I've noticed that some compilers end up generating warnings when you treat a negative number as unsigned in operations, so instead of writing '-1u', we can notice that negative one, is really the same as NOT 0, so we can instead write '~0u'. This will do the same thing, and is generally better to do since it won't generate the compiler errors.

So its nicer to do:

int main() {
    unsigned int x = ~0u; // Unsigned int max
    unsigned int y = 0;   // Unsigned int min
    return 0;
}

Now that we know this trick for unsigned ints, lets think of signed integers.
The max value for 32bit signed integers is 0x7fffffff.
If we notice though, 0x7fffffff is really (0xffffffff >> 1).
That is, signed int max, is equal to unsigned int max shifted right by one.
But since we already learned the trick on how to represent unsigned int max easily, we can use that to our advantage:

int main() {
    int x = ~0u>>1; // Signed int max
    return 0;
}

The last thing to notice for signed ints, is that the minimum value for 32bit signed ints in hex is 0x80000000, but it just so happens that that number is signed int max + 1, that is 0x7fffffff + 1.

So we can end up doing this:

int main() {
    int x = ~0u>>1;    // Signed int max
    int y =(~0u>>1)+1; // Signed int min
    return 0;
}

That about does it for integers, for floats its not as simple so I didn't talk about them here. Maybe I'll end up making another blog post about the different floating point representations...

Notes:
When doing the '-1' or '~0' tricks where you shift the value; be sure to do the shift as an unsigned operation! That is either do: ~0u>>1 or (unsigned int)~0>>1, DO NOT do ~0>>1. This will do an arithmetic shift, instead of a logical shift, and make the result be -1, instead of 0x7fffffff.

And in-case you're wondering, these tricks are not 'slower' than typing in the numbers manually. C++ compilers do something called constant-propagation and constant-folding, which converts stuff like (-1u>>1)+1 to a constant at compile-time, and therefore there's no extra overhead compared to typing 0x80000000....

Also, this will not apply to most people, but another thing to note is that some very-old/weird hardware can use one's complement integers (instead of two's complement) or some other funky stuff; when dealing with weird hardware its best to use the numeric_limits class instead of bitwise tricks, because numeric_limits assigns its values based on the specific platform. That-said, I don't even know any hardware that uses one's complement for signed integers, so these tricks are almost always safe :p

Multi-Dimensional Array Optimization

When using multidimensional arrays in c++ (or most languages for that matter), it is better to use powers of 2 for all dimensions (except for the first one which doesn't matter).

For example, take the following multi-dimensional array:
int a[3][3][3];

It will be faster to reference the elements in the following array instead:
int a[3][4][4];

The reason is that the compiler can use shifts when calculating the address to read from, as opposed to using multiplication operations. On x86 processors, this shifting by powers of 2 could even be implicit as part of the memory addressing modes which allow a shift parameter in their encoding.

So if you need speed, it could be beneficial to use powers of 2 dimensions even when you don't actually reference the extra memory. Although this optimization may require benchmarking if you increase the size of the array with too much unused data; because it may slow down the code by having less efficient cache-usage due to the extra unused memory. (in the case where all the memory will be used, then its a win-win situation)

In some cases you don't even need to increase the array dimensions to benefit from this knowledge. If you have an array "int arr[4][7];" you know it will be more efficient to swap the dimensions and just access it the other way: "int arr[7][4]".

Using c++ references for nicer code

It is common to see castings and conversions between different types of primitives in c++ code.
Many times however you don't want to do any conversion of the value, but instead just want to reference the binary representation of the variable as another type.

The common ugly way to do this is something like this:

// Program Entry Point
int main() {

    // Make x hold the binary representation of a 
    // positive infinity float
    int x = 0x7f800000;

    // Treat x as if it was holding a float instead of an int,
    // and then give f the same value
    float f = *(float*)&x;

    // Print float f (positive infinity) to the console
    cout << f << endl;
    return 0;
}

This does work, however as you can see the second line of code is pretty ugly.
The reason you can't just do "float f = (float)x;", is because that would mean you're casting the int value to a float; so the value is actually converted to a floating point value.

But that's not what we wanted, we instead want the 'int x' to behave as it was a float the entire time; that is why we first take the address of 'x' (&x), then treat it as a float pointer ((float*)&x), then finally dereference it back (*(float*)&x).

With c++ however, you can use references to simplify this whole procedure.

// Program Entry Point
int main() {

    // Make x hold the binary representation of a 
    // positive infinity float
    int x = 0x7f800000;

    // Treat x as if it was holding a float instead of an int,
    // and then give f the same value
    float f = (float&)x;

    // Print float f (positive infinity) to the console
    cout << f << endl;
    return 0;
}

This trick was taught to me by Jake Stine from pcsx2, and its something not a lot of coders know apparently, because I commonly see people using the ugly-way to do this instead.
Most-likely because you can't do this in normal C (just another reason why C sucks compared to C++ xD).

Fast Multiplication and Division

Another well known bitwise trick is that you can do multiplication and division by powers of two "2^n", with just simple shifts by "n".

For example, you can do:

// Normal Multiplication
void mul(int& x) {
   x = x * 4;
}

// Optimized Multiplication
void mul(int& x) {
   x = x << 2;
}

And for division:

// Normal Division
void div(unsigned int& x) {
   x = x / 4;
}

// Optimized Division
void div(unsigned int& x) {
   x = x >> 2;
}

Unlike the modulus optimization trick, the multiplication trick does work for both signed and unsigned variables, so the compiler is safe to optimize these cases for you.

In the case of the division trick there is a problem that may happen if you have a negative signed number. If you divide a negative integer and the result should have a remainder, then using shifts may give you the wrong result (for example, -1/2 should be 0, but -1>>1 is -1).
Compilers are able to optimize signed division by powers of two using shifts and interesting logic to account for the possible errors.

For the reason that compilers will make the necessary optimizations for you, it is generally better to leave the code as normal multiplications and divisions for readability and to prevent mistakes.
If you're dealing with low level assembly, you'd obviously want to be doing the shifts where possible instead of using mul and div.

Fast Modulus Operation and Using Unsigned Ints as an Optimization

This is another pretty well-known trick; but there is often a few misconceptions with it.

If you are using the modulus operator '%' with a power of 2 value '2^n', then you can do the same operation with a bitwise AND with 2^n-1.

// Normal Mod Operation
void mod(unsigned int& x) {
  x = x % 4;
}

// Optimized Mod Operation
void mod(unsigned int& x) {
  x = x & 3;
}

It is very important to note that this only works with positive/unsigned values.
If x was '-6' for example, the correct value returned should be '-2', but with the optimized mod it would return '2'.

The optimized mod trick however is very useful as perhaps one of the most common uses of Mod is to check if a number is odd or even:

// Normal isEven Operation
bool isEven(int x) {
  return !(x % 2);
}

// Optimized isEven Operation
void isEven(int x) {
  return !(x & 1);
}

This works regardless if the input is positive/unsigned, and is much faster than using the modulus operator.

The way the Modulus operator works in x86-32 is it has to do a Div operation, and get the remainder; Div is almost always a slow operation on any architecture.


I also wanted to point out something else.
The misconception some people have is that the compiler already will optimize something like "x = x % 2" into "x = x & 1", well the real answer is not-always.

As I already said, the optimization only works for positive/unsigned values, so if you declare x as a normal signed-int, then the compiler can't safely optimize the operation into an AND.
This is why I wanted to point out that using "Unsigned Int" can be an optimization because the compiler will be able to change such mod operations into bitwise ANDs.

If you leave the values as signed, the compiler either does one of 2 things:
1) Will just compile it using a div and get the remainder.
2) Will compile code that checks the sign bit of value, does the optimized AND, and negates the value if the original value was negative.

That is, the compiler will do something like this:

// What the compiler might generate for
// "x = x % 2;" with signed values
if (x < 0) {
    x =  x & 1;
    x = -x;
}
else x = x & 1;

Many times I have seen code where performance has increased dramatically from removing modulus operations in favor of bitwise ANDs or other logic.

For example, if you were to have a loop like this:

for(int i = 0; i < 100000; i++) {
    someVar++;
    someVar%=7;
    // ... Do more stuff
}

You can make it much faster by doing this:

for(int i = 0; i < 100000; i++) {
    someVar++;
    if (someVar >= 7) someVar = 0;
    // ... Do more stuff
}

Bitwise Set-Bit

Say you want to set a variable to '0' if an integer is 0, and '1' if an integer is non-zero.

You can do it this way:

int setBit(int x) {
    return !!x;
}

If you want to instead emulate this behavior, you can do it some other ways.

If you know for sure the sign-bit is not set, then you can implement this behavior like this:

int setBit(int x) {
    return (uint)(x + 0x7fffffff) >> 31;
}

This works because if any bits were set, then it ends up carrying a '1' over to bit #31 (the sign bit).

If you also want to include the sign bit into this, you can implement the setBit() function like this:

int setBit(int x) {
    return (((uint)x >> 1) | (x&1)) + 0x7fffffff) >> 31;
}

Or you can use 64bit operations like this:

int setBit(int x) {
    uint64 y = (uint64)(uint)x + 0xfffffffful;
    return ((int*)&y)[1];
}

Notes:
This trick isn't really useful when sticking to high level c++, but it can be useful when dealing with low level assembly.

With x86 if you don't wish to use the SETcc instruction, you can use a variation of the trick for full 32bit detection using the carry bit like so:

    add eax, -1 // Add 0xffffffff to eax
    rcl eax,  1 // Rotate with the carry bit so its in the lsb
    and eax,  1 // AND with the carry bit

The above is nice because SETcc only sets the lower byte to 1/0, while this will set the full 32bit register to 1/0. Also because SETcc only modifies the lower byte, it can be a speed penalty with the CPU's pipeline as opposed to modifying the full 32bit register.

Also note that I use 'int' and 'uint' in this article to refer to 32 bit signed and unsigned ints.
And i use 'uint64' to refer to unsigned 64bit int.

Testing for NaN and Infinity values

From my work on pcsx2 I have had to deal extensively with the problem of NaN and Infinity values with floats.

The ps2's FPU and VU processors do not support NaN or Infinity values, so it is a pain to emulate them on a system that does support such values (x86-32/SSE processors).

There are a variety of ways to test for NaN and Infinity values, and I will list a few here.

The first is pretty well known.
If you compare a float for equality against itself, it should return True unless the float is a NaN.
So the typical approach is to do something like:

// Test for NaN
bool isNaN(float x) {
    return x != x;
}

That will only test for NaN's, if you want to check for infinities you can do something like this:

#include <limits>
#include <math.h>

// Test for positive or negative infinity values
bool isInf(float x) {
    return fabs(x) == numeric_limits<float>::infinity();
}

You can instead use bitwise logic to test for NaN's and Infinities.

// Test for NaN with bitwise logic
bool isNaN(float x) {
    return ((int&)x & 0x7fffffff) >= 0x7f800001;
}

// Test for Inf with bitwise logic
bool isInf(float x) {
    return ((int&)x & 0x7fffffff) == 0x7f800000;
}

You can even check for both NaN and Infinities with just one comparison:

// Test for NaN or Inf with bitwise logic
bool isNaNorInf(float x) {
    return ((int&)x & 0x7fffffff) >= 0x7f800000;
}

Generally you probably don't want to use the bitwise version of these functions for the reason that the compiled code will end up having to switch from FPU to integer arithmetic, which will most likely end up being slower than sticking to the floating point comparisons.

Compare Optimization Tricks

Okay I invented these bitwise tricks myself, so they shouldn't be as well known as the last one I posted; well the first one is more obvious (so probably other people have used it), but the other one not so much.

If you're ever comparing an integer being in the range 0...n, you can normally do this:

// Normal Compare
bool compare(int x) {
    return (x >= 0) && (x <= 10)
}

However, you can do that same operation with just one compare instruction:

// Optimized Compare
bool compare(int x) {
    return (unsigned int)x <= 10;
}

Now this second trick is if you want to compare 2 different integers, and want to check if they're both in the range 0...2^n

Normally you could do this:

// Normal Compare
bool compare(int x, int y) {
    return (x >= 0) && (x <= 16)
        && (y >= 0) && (y <= 16);
}

Using the trick mentioned before, we figured out you can optimize it to this:

// Optimized Compare
bool compare(int x, int y) {
    return ((unsigned int)x <= 16)
        && ((unsigned int)y <= 16);
}

But now we can further optimize this to just one single compare!

// Very Optimized Compare!
bool compare(int x, int y) {
    return ((unsigned int)(x|y) <= 16);
}

That ends up doing the work of 4 comparisons, with just 1!
(Although you now have the added OR instruction; but OR is very fast to compute on almost every processor).

I want to stress again that the last optimization only works when the value is a power of two (2^n).

xor swap trick and add/sub swap trick

This is a pretty common bitwise trick most veteran coders know about, but its probably a good bitwise trick to start this section out with.

If you have 2 integers, x and y, you can swap their values normally by doing:

// Normal Swap Function
_f void swap(int& x, int& y) {
    int z = x;
    x = y;
    y = z;
}

But this requires a temporary variable/register to be used (the "int c").

You can do this same functionality without using a temporary variable at all, using the xor swap trick:

// XOR Swap Function
_f void swap(int& x, int& y) {
    assert(&x != &y);
    x ^= y;
    y ^= x;
    x ^= y;
}

The result ends up being the same as the first function, but notice now it doesn't use any temporary variables.
This trick can be useful if you're doing some low-level asm work, or reg-alloc in a recompiler, or for any reason you don't have an extra register to spare and your instruction set doesn't have an xchg opcode. Admittingly, if you're just sticking to c++ code, might just be better to use the normal swap routine instead.

Also beware! This trick has a big problem if &x == &y, that is, if x and y are the same exact variable. In that case instead of keeping the values the same, you end up zeroing out the value!
So the xor swap trick should only be used when you know you are dealing with 2 distinct 'x' and 'y' variables. That is why we put the assert(&x != &y) line in this function, so on debug builds we will get an error if the references of x and y point to the same exact variable.

Lastly I'll point out that you can do the same trick using add and sub operations, but its a bit messier and not as useful:

// Add/Sub Swap Function
_f void swap(int& x, int& y) {
    assert(&x != &y);
    x += y;
    y  = x - y;
    x -= y;
}

The problem with this code is the second instruction.
For many instruction sets (for example SSE, MMX, or x86-32), you're stuck with "dest, src" syntax for instructions.
This means that the compiled code for this will still end up having to use some type of temporary register or the stack to compute this.

If you're dealing with another architecture however that has 3-operand syntax "dest, src1, src2", then this is more useful since you can do the second line with just 1 instruction.

Notes:

I use "_f" as a macro for "__forceinline" so:

// Forceinline Macro for in-lining functions
#define _f __forceinline

Also note that this trick can be extended to be used with floats, doubles, and etc...
But you have to be sure to do the operations as 32bit integers or 64bit integers respectively.

Here's an example of swapping 2 floating point singles with this trick:

// Add/Sub Swap Function
_f void swap(int& x, int& y) {
    assert(&x != &y);
    x ^= y;
    y ^= x;
    x ^= y;
}

// Float Swap Function
_f void swap(float& x, float& y) {
    swap((int&)x, (int&)y);
}

Technically this isn't very useful when sticking with high-level c++, especially since floating point operations are generally compiled to use the x87 fpu (so the floats will be moved back into gprs, and end up being slower than a regular swap); also this will confuse the compiler more so that's another reason it won't generate as good code; but if you're dealing with SSE directly, the xor trick can be useful.