HN Explorer

16 comments

[ 3.2 ms ] story [ 47.2 ms ] thread
swingline-747
Btw, XOR swap... probably slower than register-aliased swap, but it swaps two registers without using a third:

    void swap(char *s, int a, int b)
    {
       s[b] ^= s[a];
       s[a] ^= s[b];
       s[b] ^= s[a];
    }
ur-whale
You'd better hope that a!=b
scj
Why would a==b be a problem with the XOR swap trick?

  function xorSwapTest(min, max) {
    for (var i = min; i < max; i++) {
      var a = i, b = i;
      b ^= a;
      a ^= b;
      b ^= a;

      if (a != i || b != i)
        throw Error("Problem with " + i);
      }

    return true;
  }
saagarjha
The issue is that if a == b, &s[a] == &s[b]; i.e. you're writing to the same address.
saagarjha
Most compilers will optimize this to whatever is faster even if you use the clearer version.
and-then
You're making a sweeping, laughably-false assertion. Clearly you don't understand how compilers work. C compilers are not miraculous magic boxes. They have limited information and limited optimizations. It's very likely an obscure implementation of an algorithm will more-or-less translate one-to-one to nearly equivalent assembly because the compiler can't analyze it.
saagarjha
I think you've misrepresented what I said, which was that the compiler is good enough to pick between a register or XOR-swap (in the comment I was replying to), based on the architecture and calling sites.
foota
The "Clearly you don't understand how compilers work" portion of this comment is unnecessary.
ur-whale
While this is very cool, I'm having a hard time believing it is a new development.
pharrington
Standard procedure is to do something like requesting the mods add "2001" to the title.
FabHK
Or, in this case, "(<1400)".
chrisweekly
lol -- would likely want to include "A.D." to be clear it's a date!
mauricioc
According to Donald Knuth, "This algorithm goes back to Nārāyaṇa Paṇḍita in 14th-century India; it also appeared in C. F. Hindenburg's preface to _Specimen Analyticum de Lineis Curvis Secundi Ordinis_ by C. F. Rudiger (Leipzig: 1784), xlvi--xlvii, and it has been frequently rediscovered ever since". (Volume 4A, Section 7.2.1.2, Algorithm L)
svat
Indeed this is precisely Algorithm L of section 7.2.1.2 “Generating all permutations” (described on its very first page [1]), and is also what is used by C++'s `next_permutation`, among others. There are a few expositions of it online [2] (including this 2008 StackOverflow answer of mine: [3]).

[1] Draft version of Knuth's Fascicle 2B: http://www.cs.utsa.edu/~wagner/knuth/fasc2b.pdf#page=5 (now page 319 of Volume 4A)

[2]: https://www.quora.com/How-would-you-explain-an-algorithm-tha...

[3]: https://stackoverflow.com/a/353248/4958