Search code examples
c++xor

Swap two variables with XOR

With the following method we can swap two variable A and B

A = A XOR B
B = A XOR B
A = A XOR B

I want to implement such a method in C++ that operate with all types (int, float, char, ...) as well as structures. As we know all types of data including structures take a specific space of memory, for example 4 bytes, 8 bytes

In my opinion this method for swapping must work with all types excluding pointer based types, It should swap memory contents, that is bits, of two variables

My Question
I have no idea how can I implement such a method in C++ that works with structures (those does not contain any pointers). Can any one please help me?

Solution

  • Your problem is easily reduced to xor-swap buffers of raw memory. Something like that.

    void xorswap(void *a, void *b, size_t size);

    That can be implemented in terms of xorswaps of primitive types. For example:

    void xorswap(void *a, void *b, size_t size)
{
    if (a == b)
        return; //nothing to do

    size_t qwords = size / 8;
    size_t rest = size % 8;

    uint64_t *a64 = (uint64_t *)a;
    uint64_t *b64 = (uint64_t *)b;
    for (size_t i = 0; i < qwords; ++i)
        xorswap64(a64++, b64++);
    uint8_t *a8 = (uint8_t*)a64;
    uint8_t *b8 = (uint8_t*)b64;
    for (size_t i = 0; i < rest; ++i)
        xorswap8(a8++, b8++);
}

    I leave the implementation of xorswap64() and xorswap8() as an exercise to the reader.

    Also note that to be efficient, the original buffers should be 8-byte aligned. If that's not the case, depending on the architecture, the code may work suboptimally or not work at all (again, an exercise to the reader ;-).

    Other optimizations are possible. You can even use Duff's device to unroll the last loop, but I don't know if it is worth it. You'll have to profile it to know for sure.