2 ms·
the calculation of addresses for the XOR swap I'd be interested to know more about the internal implementation, but I don't think that address calculation uses
by nkurz 11y ago
the calculation of addresses for the XOR swap
I'd be interested to know more about the internal implementation, but I don't think that address calculation uses any additional registers (physical or logical). There are multiple execution ports dedicated to address generation, and I think they are self-contained.
multiple CPU registers to do the abs()
Likely yes for any library implementation, although this made me wonder if it's possible to do it in-place with constants. Turns out it is, Hacker's Delight to the rescue:
abs(x) == ((x >>> 30) | 1) * x
http://hackersdelight.org/basics2.pdf http://hackersdelight.org/basics2.pdf
- prmichaelsen 11y agoThanks for putting the abs() part to rest. I included it for the sake of having the final code be a little more readable. But yes, indeed, it is possible once more to use bit-wise manipulation to achieve elegant solutions! Thanks for reading! And of course, thanks for posting this blog post, nkurz!
- deleted 11y ago[deleted]
- userbinator 11y agoThere's no memory-to-memory XOR in x86. A XOR swap will need one register, the array address itself will take another, and the "single integer variable" one more. Then you also need the absolute value of the variable; there's another register. The single-expression abs that you specify needs at least two registers, one to hold the shifted value and one to hold the original one. Two alternatives which do not involve multiplication and are 3 instructions is here: https://www.strchr.com/optimized_abs_function https://www.strchr.com/optimized_abs_function