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?
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 xorswap s 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.
You could use Bitwise XOR "^" in C to XOR two bits. See here and here. Now to XOR 'a' and 'b' start XORing from the east significant bit to the most significant bit.
上一篇: 交换扩展到两个以上的变量？
下一篇: 用XOR交换两个变量