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

21–30 of 243 posts

Re: That XOR Trick (2020)

#21

Post by exabrial »

> There are a whole bunch of popular interview questions

As a very personal strong opinion, this makes me groan.

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

I'd rather know whether or not they are a pleasant person, are a team player, whether they have leadership aspirations, and take responsibility.

Re: That XOR Trick (2020)

#23

Post by mytailorisrich »

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…

xor reg, reg is indeed the standard way to zero out a register in x86 assembly (it's not just a compiler trick) as it is both shorter and faster than loading the register with zero via a mov.

Apart from that, I'd say that a common use of XOR operations in general are interactions with hardware peripherals where manipulating bit fields are needed.

Re: That XOR Trick (2020)

#24

Post by FartyMcFarter »

nickelpro wrote: post #19
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…

Xor'ing registers isn't a compiler trick or arcane piece of lore, it's the canonical way to zero a register on most architectures. It's the only universally recommended way for both Intel and AMD x86 and x64 processors.

In fact, modern x86 CPUs know that the result of "x XOR x" is independent of x, and use this fact to optimize operations that would otherwise have a dependency.

Re: That XOR Trick (2020)

#25

Post by ml_giant »

j-pb wrote: post #10

Ah off by one errors are hard: > 1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 1] should be > 1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 2] Because a 0 indexed array of length n-1, has n-2 as it's last index. After all, it's missing a value.

Let's try an example with n=4:

1 ^ 2 ^ 3 ^ 4 ^ A[0] ^ A[1] ^ A[2] ^ A[3]

It might be early in the morning and I am missing something, but it has n-1 as its last index. Any insight is appreciated :)

Edit: There is a missing number in the array, thus its last index is n-2. Thanks for the correction, OP.

Re: That XOR Trick (2020)

#26

Post by tyingq »

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.

Re: That XOR Trick (2020)

#28

Post by bonzini »

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

A somewhat common use of XOR is p != q. It is actually an XOR. Another useful way to think of XOR is "either p or q is true, but not both, and not neither."

Compilers can optimize "a != b" to "a xor b" if they know that both operands are 0 or 1. There are crazy many expression rewriting rules.

Re: That XOR Trick (2020)

#29

Post by z3rgl1ng »

nickelpro wrote: post #19
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…

Xor'ing registers isn't a compiler trick or arcane piece of lore, it's the canonical way to zero a register on most architectures. It's the only universally recommended way for both Intel and AMD x86 and x64 processors.

Hey, I didn't know this. I'm glad they shared it. Maybe instead of being a jerk, you could say:

"Yes, as a matter of fact it's the canonical way..."

Re: That XOR Trick (2020)

#30

Post by smlckz »

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

(n+1)%2 = if (n+1) is divisible by 2 then 0 else 1 = (n+1) & 1 = ~(n & 1)

((n + (n % 2)) // 2) % 2 = ((n + (n & 1)) >> 1) & 1 = ((n & 2) >> 1) ^ (n & 1) = (n ^ (n >> 1)) & 1

In human terms, that means XOR of 1, 2, ..., n is: (if (n is divisible by 2) then n else 0) + (if ((if (n is divisible by 2) then n else n + 1) is divisible by 4) then 1 else 0)

Or, as code: n * ~(n & 1) + (n ^ (n >> 1)) & 1

Phew! Can this be made any simpler or smaller?

1 ^ 10 = 11, 11 ^ 11 = 0, 0 ^ 100 = 100, 100 ^ 101 = 001, 1 ^ 110 = 111, 111 ^ 111 = 0, 0 ^ 1000 = 1000, ...

----

If you have some time, take a pen and a paper and think it through, you'll really like it...

Post reply on HN