The following example shows the array reversing using the XOR operator. No need to take any additional variable to reverse the array.
int main(int argc, _TCHAR* argv[]) { char str[] = "I AM STUDENT"; int length = strlen(str); for(int i = 0; i < ((length/2)); i++) { str[i] ^= str[length - (1+i)]; str[length - (1+i)] ^= str[i]; str[i] ^= str[length - (1+i)]; } cout << str << endl; return 0; }
The above example is one of the uses of XOR but XOR comes in handy when we can do branchless coding methods like butterfly switch etc. Sometimes this is very effective in speeding up the execution. Let's see one of the uses of XOR in branchless coding. I am taking a simple example of Y = | X |. Yes, I am generating abs of a supplied number. So, my function signature/definition in C++ looks like below:
int absoluteBranch(int x){if (x < 0){return -x;}else{return x;}}
From the C++ code, we can see the branching in code and until runtime, we can't
definitely say which branch could be executed. If we look at the assembly generated
by the code also shows branching (Without optimization):
definitely say which branch could be executed. If we look at the assembly generated
by the code also shows branching (Without optimization):
absoluteBranch(int):push rbpmov rbp, rspmov DWORD PTR [rbp-4], edicmp DWORD PTR [rbp-4], 0jns .L4mov eax, DWORD PTR [rbp-4]neg eaxjmp .L5.L4:mov eax, DWORD PTR [rbp-4].L5:pop rbpret
We have instructions like cmp(compare), jns(jump if not signed) andjmp (unconditional jump). With the help of XOR we can completely removethis branching of code while calculating abosolute of a signed number.
int absoluteBranchless(int x){int y = x >> (sizeof(int) * 8 - 1);return (x ^ y) - y;}Now I don't have any branch in the C++ code and assembly generated out ofit also branchless. Here goes the assembly (Without optimization):absoluteBranchless(int):push rbpmov rbp, rspmov DWORD PTR [rbp-20], edimov eax, DWORD PTR [rbp-20]sar eax, 31mov DWORD PTR [rbp-4], eaxmov eax, DWORD PTR [rbp-20]xor eax, DWORD PTR [rbp-4]sub eax, DWORD PTR [rbp-4]pop rbpretThe SAR instruction shifts the MSB and it became all FFs. For positive number it's all 00s.So for negative number mask became -1 (in two's complement) and for positive numberit will always be 0. We then XOR the number with mask and subtract with mask, whicheffectively adds +1 in case of negative number and +0 for positive number.In above example variable y is the mask value.It's nice, we have no branching!
Comments
If you cannot afford any extra memory for a new array then this XOR-ing is a good solution.I believe its used in hardware which cannot afford huge memory.