Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

That XOR Trick (2020)

florian.github.io

Post reply on HN
Print view View original

181–190 of 243 posts

Re: That XOR Trick (2020)

#181

Post by steveklabnik »

gnull wrote: post #160
jfk13 wrote: post #141

Earlier quoted context omitted.

That's not necessarily abuse; it may be quite appropriate to explicitly limit something's lifetime.

Indeed! I somewhat over-use this in Rust to initialize an immutable variable with mutating code. let var: Vec ; // this one is immutable, will be initialized later { let mut var_; // mutable … // initialize var_ with some mutating code var = var_; // now move var_ to var, initializing the latter }

This is a bit simpler as:

  let var = {
      let mut var = ...

      var
   };
that is, you can assign the result of the block directly. That way you don't need two variables with the _ name as the second.

Re: That XOR Trick (2020)

#182

Post by bonzini »

nickelpro wrote: post #60
bonzini wrote: post #44

Earlier quoted context omitted.

Not necessarily true for most architectures. Many RISC architectures have a "zero" register, so a canonical "move short immediate" instruction could be "OR Rn, R0, #n" ("OR R0 which is always zero with n and store into Rn") or the same with ADD. Then clearing Rn will usually be "OR Rn, R0, R0", "ADD Rn, R0, #0" or something like that.

I should have been clearer, when I say most architectures I mean most x86/x64 architectures not most ISAs. Obviously ISAs with a dedicated zero register don't need the zeroing idioms of x86.

In that case it's all of them. Some might like having both a MOV and a XOR in some special cases (one to avoid partial register stalls and one to avoid partial flags stalls, if I remember correctly) but even in those cases it's usually easy enough to avoid partial register stalls in some other way and just use XOR.

Re: That XOR Trick (2020)

#183

Post by zerd »

gnull wrote: post #160
jfk13 wrote: post #141

Earlier quoted context omitted.

That's not necessarily abuse; it may be quite appropriate to explicitly limit something's lifetime.

Indeed! I somewhat over-use this in Rust to initialize an immutable variable with mutating code. let var: Vec ; // this one is immutable, will be initialized later { let mut var_; // mutable … // initialize var_ with some mutating code var = var_; // now move var_ to var, initializing the latter }

You can also initialize it to an expression, e.g.

    let var = {
      let mut var_ = Vec::new();
      var_.push(1u32);
      var_
    };

Re: That XOR Trick (2020)

#184

Post by EmielMols »

user-the-name wrote: post #129
surajrmal wrote: post #123

Earlier quoted context omitted.

The bigger problem with this approach is that you can't remove/erase something from the list just by knowing it's address. This is a key mechanism for most use cases. However, if you're fine with limiting yourself to erasing only during iteration, it's pretty nifty. I've also done some benchmarks in the past and found it interior iteration performance due to what I'm assuming to be inability to prefetch the next addr…

Also, I think this may be the only data structure I have heard of that has an O(1) reverse ordering operation?

Ha, very nice!

To clarify: to reverse the list, one would only have to swap the HEAD and TAIL pointers of the base structure.

Re: That XOR Trick (2020)

#185

Post by wizzwizz4 »

gnull wrote: post #160
jfk13 wrote: post #141

Earlier quoted context omitted.

That's not necessarily abuse; it may be quite appropriate to explicitly limit something's lifetime.

Indeed! I somewhat over-use this in Rust to initialize an immutable variable with mutating code. let var: Vec ; // this one is immutable, will be initialized later { let mut var_; // mutable … // initialize var_ with some mutating code var = var_; // now move var_ to var, initializing the latter }

Couldn't you just write:

  let var: Vec = {
    let mut var_;
    …
    var_
  };
Or, better still:

  let mut var: Vec;
  …
  let var = var;

Re: That XOR Trick (2020)

#186

Post by wizzwizz4 »

strulovich wrote: post #173
user-the-name wrote: post #129

Earlier quoted context omitted.

Also, I think this may be the only data structure I have heard of that has an O(1) reverse ordering operation?

Wouldn’t this be achieved by an array and a Boolean flag just as well?

Technically, but I'm not quite sure that's in the spirit of things.

Re: That XOR Trick (2020)

#187

Post by taejo »

simias wrote: post #46

Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables alway…

Did you use this in a contest? I seem to remember this exact thing being used to leak data in a contest.

Re: That XOR Trick (2020)

#188

Post by volta87 »

strenholme wrote: post #140

The thing about the “Use XOR to swap two variables” trick is that it’s a version of this solution which works for any two real numbers (or integers): a = a - b b = a + b a = b - a XOR is simply addition or subtraction modulo 2 for each bit, so making the above XOR looks like this: a = a ^ b b = a ^ b a = b ^ a

The article touches on this, since its an important realization. In C, however, if the integers are not unsigned, the add/sub version exhibits UB on overflow, because C unnecessarily ties signed/unsignedness with overflow behavior (UB, two's complement, etc.).

Not that this is important, but could hint why this trick is more often shown with XOR than with add/sub.

Re: That XOR Trick (2020)

#189

Post by bonoboTP »

ravi-delia wrote: post #172
bonoboTP wrote: post #139

Earlier quoted context omitted.

The attitude is often quite strange. Like on Twitter I saw a few days ago that many were riled up about the fact that a prof would ask how to solve Ax=b (linear algebra) for a deep learning / computer vision PhD position. People were calling this unnecessary gatekeeping ... I'm like that's just a warm-up question to get comfortable... But apparently the loud online hive mind opinion is that all that should count is s…

Except solving linear functions has a clear role in any field that makes use of linear algebra. Interviews that require memorizing volumes of pointless trivia unrelated to the work at hand are completely different.

Yes, in practice this interview style now achieves exactly the opposite goal that it was created for. That is, originally people wanted to base hiring on general problem solving skill, mapping out a problem domain with relevant questions, proposing solutions, identifying tradeoffs, reacting to a change in problem statement, etc. based on a pure computer science foundation, independent of ever changing software frameworks, libraries, APIs etc. Precisely because memorizing the specific steps of creating a CRUD mobile app in today's workflow is not useful later on. The problem is, Goodhart's law kicked in and performance in such puzzles became the target to optimize for, so it stopped being a good measure, because now people have to explicitly study for it from books and online courses and practice sites and so now it measures more of the effort you're willing to put in to jump hoops instead of actual problem solving aptitude.

An alternative could be to ask about a recent real-world project of the applicant, but that's also easier to rehearse.

Post reply on HN