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

161–170 of 243 posts

Re: That XOR Trick (2020)

#161

Post by sixstringtheory »

jfk13 wrote: post #141
simias wrote: post #136

Earlier quoted context omitted.

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...

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

As an example, in our C++ codebase at work we always place mutex locks inside their own scope blocks along with the critical sections of code they’re synchronizing. Helps readability and the scope determines when the mutex is released.

Re: That XOR Trick (2020)

#162

Post by crazydoggers »

My favorite trick is the XOR one time pad. XOR anything (text, images, etc) with a random pad or "key" the same length as the data your are encrypting... and you've got an completely unbreakable cipher.

Just be careful as with any one-time-pad cipher. The key needs to be the same length as the data, generated randomly, and you can only use it once... no key reuse ever.

Re: That XOR Trick (2020)

#163

Post by cuspycode »

trinovantes wrote: post #16

Xor trick may reduce the time/space complexity of a solution but I'd say it definitely increases the cognitive load (maintenance) complexity. Outside of few niche industries/use cases, the increased developer cost will probably outweigh whatever extra hardware you'd need to compensate.

Agreed, the XOR trick is just a clever trick that might be useful in some esoteric niche cases, but otherwise don't bother. GCC will even optimize away the XOR operations when this is used for simple things like ints on amd64. I did a simple compile test, and with -O1 and higher I got identical machine code for the XOR algorithm and the naive swapping version. Without optimization I did get the XOR instructions, but the number of machine instructions was longer than for the naive case, and the number of CPU registers used was the same.

Re: That XOR Trick (2020)

#164

Post by [deleted] »

johnfn wrote: post #53
tlb wrote: post #3

> XOR all values between 1 and n An O(n) algorithm!? You'd expect there to be a closed-form solution for this, analogous to summing a series using n*(n-1)/2. OEIS to the rescue. http://oeis.org/A077140 gives ((n+1)%2)*n + (n+(n%2))//2 % 2

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

[deleted]

Re: That XOR Trick (2020)

#165

Post by layer8 »

loeg wrote: post #152
layer8 wrote: post #137

Earlier quoted context omitted.

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

Your linked comment only quotes excerpts saying it's implementation-defined, rather than undefined. Can you point to the part that is undefined? (You would use a uintptr_t for the xor'd prev-next pointers instead of void*.)

To be precise, it's implementation-defined whether it's undefined behavior, prior to C11. You are right that in C11, if uintptr_t is used to store the xored value, behavior is defined.

Re: That XOR Trick (2020)

#167

Post by ellis-bell »

tyingq wrote: post #26
danpalmer wrote: post #4

As mentioned in this article, x ^ x == 0. Fun fact, this is frequently used by compilers as a "cheap" way to zero out a register. In addition, there are comparatively few cases in programming where we XOR. Sure, it happens in things like games quite a lot, but the main use is actually _cryptography_. Between these two facts (more like hints really), I managed to reverse engineer the bulk of a piece of malware I was g…

"In addition, there are comparatively few cases in programming where we XOR. Sure, it happens in things like games quite a lot, but the main use is actually _cryptography_" I'd be curious if that's actually true. I know XOR is used for non-cryptographic checksums, parity bits, maintaining key traversal order for associative arrays, overflow detection, etc. Lots of general purpose "stuff" that isn't cryptography.

XOR is used a ton in the theoretical underpinnings of cryptography. It's used in the one time pad which is essentially the "smallest" cryptographic scheme that is perfectly secure (perfectly secure has a mathematical definition in this context, it's not saying there can never be any attacks).

In general the reason why is that if you have two random variables x and y, where x has any distribution (so for example x could even be "attack normandy on june 6" with certainty) and y is uniformly distributed across all n-bit strings (so it could be any string of n zeros and ones with equal probability), then you can show that x ^ y appears as if it is also uniformly distributed across all n-bit strings as well.

Because of this property it's used frequently in many higher order methods as well.

Re: That XOR Trick (2020)

#168

Post by rcoveson »

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 do something like this in "modern" Java to get for-each with index:

    { int i = -1; for (V v : list) { i++;
        // stuff
    } }
While declaring i = -1 to start is a little gross, I like that it has some of the same properties as a normal for loop. No effect on parent scope, and all loop-logic is concentrated on the first (textual) line.

Re: That XOR Trick (2020)

#169

Post by tobinfricke »

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…

People like to harp on C++, but templates permit code that is simultaneously maximally clear and efficient:

#include

swap(s[i], s[j]);

Re: That XOR Trick (2020)

#170

Post by ynfnehf »

I have never gotten the point of this trick. Don't basically all processors have some equivalent of XCHG (swap contents of two registers)? Even the 8086 had it back in 1978. (The z80 doesn't have it, but it is a couple of years older than 8086.)

I tried searching the LLVM source for any mention of the trick, but couldn't find anything. So I can't see it having any relevance to modern CPUs.

Post reply on HN