News for hackers. Stuff that matters.
Re:Sort an array using only one local variable by userbinator on Saturday April 23, 2016 @12:09PM (#11556108)
It's "one local variable" in the same way as

    struct {
        unsigned int theint:31;
        unsigned int thebool:1;
    } myvar;
and the code probably uses multiple CPU registers to do the abs(), the calculation of addresses for the XOR swap, etc. but still interesting just for the artificial constraint part of "can it be done".

Aside: this is one of those pages that shows everything but the actual post content(!) if you have JS disabled. And if you view the source code... you'll find a huge JSON object with the actual content, apparently just pure HTML embedded as a string inside it.

Note to readers: I am looking into a different platform for publishing my computer science articles. The current platform I am using is easy to use. However, it has its limitations. Not the least of which is the inability to use custom HTML where it is useful. This makes me unable to embed nice code snippets in my articles.

How about a simple HTML page?

Re:Sort an array using only one local variable by nkurz on Saturday April 23, 2016 @01:21PM (#11556427)
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
Re:Sort an array using only one local variable by userbinator on Sunday April 24, 2016 @12:35AM (#11558564)
There'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

Re:Sort an array using only one local variable by prmichaelsen on Sunday April 24, 2016 @12:24AM (#11558545)
Thanks 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!