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

101–110 of 243 posts

Re: That XOR Trick (2020)

#101

Post by patrec »

sleavey wrote: post #65
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…

I sometimes use your "bug" on purpose in tests, when checking that two values are either both defined or both undefined, but not one defined and one undefined: $ python >>> a, b = 1, 2 >>> bool(a) ^ bool(b) False >>> a, b = 1, 1 >>> bool(a) ^ bool(b) False >>> a, b = None, None >>> bool(a) ^ bool(b) False >>> a, b = None, 1 >>> bool(a) ^ bool(b) True (Note: this doesn't work if a value can be 0, because bool(0) is Fa…

You are aware that ^ on a 1 bit value (like a boolean) is just !=, right?

Re: That XOR Trick (2020)

#102

Post by abhishekjha »

blauditore wrote: post #12

This is conceptually almost the same as summing over all entries and comparing to the sum of all numbers in [1, n], except that the latter can be done more efficiently because that sum is simply n*(n+1)/2. There are in fact legit use cases for XOR to speed things up or make algorithms simpler, but this is not the case here IMHO.

XOR handles overflow better than the summing mechanism.

Re: That XOR Trick (2020)

#103

Post by dragontamer »

shiftingleft wrote: post #92
dragontamer wrote: post #56

Earlier quoted context omitted.

> I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). Erasure correction is a very useful trick for data-engineers. I don't think this is a microcontroller trick, as much as a data-r…

I think in erasure coding you typically know the locations of the erasures: If a disk fails, you know which one failed. However, I don't see how you would know the locations in this problem? Maybe you can elaborate on how this problem relates to erasure coding?

Bingo, you're correct.

> However, I don't see how you would know the locations in this problem?

Well, that's just from the blogpost itself:

> Application 2: Finding the Missing Number

> You are given an array A 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.

We can "find the missing number", but we don't know where to "put" the missing number. If you want to put the "missing number" back into the sequence, you still need to know the location to put it into from some other mechanism. (Ex: hard drive #5 failed, so you know to put the number into slot#5).

----------------

Application 4 starts to get into "partitioning", which is getting dangerously close to sparse parity-check matrix and LDPC graphs.

Re: That XOR Trick (2020)

#104

Post by alowe »

Thorham wrote: post #96
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…

You're wrong. Remember that XOR works on individual bits. If what you're saying was true, then swapping bits that are both set to 1 would also fail, which means this algorithm wouldn't work at all. Edit: Ignore this post, I misread the original post as saying swapping the same values would fail.

They're not saying swapping equal valued variables breaks it. It's when the pointer is the same, using the trick to swap a variable with itself will set the variable to 0.

Re: That XOR Trick (2020)

#105

Post by [deleted] »

Thorham wrote: post #96
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…

You're wrong. Remember that XOR works on individual bits. If what you're saying was true, then swapping bits that are both set to 1 would also fail, which means this algorithm wouldn't work at all. Edit: Ignore this post, I misread the original post as saying swapping the same values would fail.

[deleted]

Re: That XOR Trick (2020)

#107

Post by shiftingleft »

abalaji wrote: post #89
johnfn wrote: post #53

Earlier quoted context omitted.

Err... if you sum all the numbers that’s O(n) as well.

right but OP’s solution for this part of the problem is assumed to be instantaneous (ie O(0))

You probably mean O(1).

Although: that's not true for arbitrarily sized integers either. Multiplication in O(1) implies P = NP (which further implies NP = PSPACE): https://cs.stackexchange.com/a/1661/129151

Re: That XOR Trick (2020)

#108

Post by bidirectional »

whatshisface wrote: post #88
bonoboTP wrote: post #78

Earlier quoted context omitted.

Maybe you feel like you are being inclusive and warmhearted for praising soft skill vs 'teh codez skillz', but please also consider that tech and programming jobs is like the last refuge for people with high technical aptitude and perhaps less social soft skills regarding the meta political and expectation games, eg people somewhere on the autism spectrum. Perhaps such interviews are overused but if the interview is…

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.

Re: That XOR Trick (2020)

#109

Post by dahart »

Thorham wrote: post #96
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…

You're wrong. Remember that XOR works on individual bits. If what you're saying was true, then swapping bits that are both set to 1 would also fail, which means this algorithm wouldn't work at all. Edit: Ignore this post, I misread the original post as saying swapping the same values would fail.

> swapping bits that are both set to 1 would also fail

No, swapping two 1 bits works fine. Work it out more slowly, the article covered this and why it always works.

(1,1) => (1^1,1)=(0,1) => (0,1^0)=(0,1) => (0^1,1)=(1,1)

Re: That XOR Trick (2020)

#110

Post by dandanua »

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