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

131–140 of 243 posts

Re: That XOR Trick (2020)

#131

Post by Straw »

dandanua wrote: post #110
Straw wrote: post #9

You can actually extend the XOR trick for missing elements to any fixed number! The standard (non-XOR) low-memory solution calculates the sum of x, x^2, x^3, ..., x^n, which gives enough information to find the missing elements as the roots of an n degree polynomial. We can just do the same thing in the finite field F_{2^k}, where k is the bitwidth of the integers. Addition in this field corresponds to a bitwise XOR,…

Addition in F_{2^k} is not the same as XORing. But that summation idea is correct. To solve polynomial you can use this algorithm https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algo...

Oh, neat, what's the runtime?

https://math.stackexchange.com/questions/1479745/relations-o...

What have we missed?

Re: That XOR Trick (2020)

#133

Post by valvar »

1MachineElf wrote: post #128
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…

n00b question: What is the ^= operator, and what language is it from?

It's bitwise XOR in C (and most other languages, I guess).

https://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B#Bit...

Re: That XOR Trick (2020)

#134

Post by black3r »

ufo wrote: post #74
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…

On the topic of intermediate variables, when I'm forced to use c89 I'm really shameless about introducing extra code blocks in the middle of other blocks. For example, {int i; for(i=0; i Still bothersome but better than having to declare everything at the top of the function, IMO.

if I was forced to use c89 I would resign and find a better job...

Re: That XOR Trick (2020)

#135

Post by slymon99 »

virgilp wrote: post #33

Slightly disappointed at the "two missing values" solution: First: one needs to realize that you can solve the "missing number" problem just as well with sums. So, if you're trying to find the "one missing number" between 1 and n, you simply subtract all values from n*(n+1)/2 (the sum of all said numbers) and you end up with the missing one. (using wrap-around semantics, you don't even need to have more bits of memor…

Sums increase in size, however. The nice part of the xor trick is your xor result will be the size of the base of the numbers (64 bits or whatever). If you are reading several tb of 64 bit integers from disk that could get larger than your memory (though unlikely, probably why you see this in kernels where memory might be more of a concern especially with embedded)

Re: That XOR Trick (2020)

#136

Post by simias »

ufo wrote: post #74
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…

On the topic of intermediate variables, when I'm forced to use c89 I'm really shameless about introducing extra code blocks in the middle of other blocks. For example, {int i; for(i=0; i Still bothersome but better than having to declare everything at the top of the function, IMO.

I agree, but I think back then I didn't know this trick.

I also abuse blocks in Rust, but it's more in order to placate the borrow checker...

Re: That XOR Trick (2020)

#137

Post by layer8 »

hyperman1 wrote: post #63

A fun party trick not mentioned here is reducing storage in a doubly linked-ish list: Normally each node stores 2 pointers: struct Node {void * prev;void * next} The trick is to use only 1 'pointer', storing prev XOR next: struct Node {void* xored;} While traversing, you remember not only the current position, but also where you came from. So forward traversal goes: next= current.xored XOR previous. Backwards also wo…

That’s undefined behavior in C though: https://news.ycombinator.com/item?id=3928788

Re: That XOR Trick (2020)

#138

Post by greggman3 »

I've been asked this question before. I don't remember if I already knew the answer or not. But....

When does this ever come up in the real world.

> You are given an array of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number.

This has happened to me in real life exactly NEVER!

I think maybe I was asked you have a list of pairs of integers except one number is missing its pair. Again, no idea where I would apply this in a real world situation.

Re: That XOR Trick (2020)

#139

Post by bonoboTP »

bidirectional wrote: post #108
whatshisface wrote: post #88

Earlier quoted context omitted.

Nobody complains about puzzles in tech interviews. People care about uncreative "did you read this book about interview questions" questions. If you want to test tech knowledge in tech interviews, ask a question that isn't in any book. That takes a lot more skill as an interviewer to pull off, but if you're a hiring manager, surely you can find someone on your team qualified to design a puzzle.

Google's policy is to extensively discuss interview questions internally, and blacklist any that are leaked. They are still complained about near-constantly on any tangentially related HN thread.

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 soft skills and that everyone is equally able. People are even calling out professors on Twitter (who then engage, for some reason) for saying they are looking for "outstanding" PhD candidates. Because this is apparently too exclusionary language, everyone is equally outstanding or something...

Re: That XOR Trick (2020)

#140

Post by strenholme »

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
Post reply on HN