Seeing this, I immediately thought of Quantum Mechanics.
X^V is like the superposition of X and V, but it acts more like entanglement. Given one of the values it immediately produces the other.
I wonder if there's a connection there, such that when you XOR with the observer, it produces the desired value. I may do a bit of research on my own about this.
Yeah! Look into CNOT gates. In gate based quantum computing, everything has to be reversible, but CNOT gates essentially are the same as XOR gates and are used to create entanglement. Whenever you have an operation that has a control of one or more qubits, it'll have the ability to potentially cause entanglement.
My first "well that's weird" xor usage trick was the first time I read x86 assembly output. Instead of storing an immediate value of 0 into a reg, you would commonly instead see xor r9 r9 instead of mov r9 0. People use xor in interesting ways from the very ground up.
What’s fun is it originated as a (officially recommended) space optimisation: xor R, R is two bytes while mov R, 0 is 5 (for 32b registers, for 64b it’s 3 and 7). And as long as CPUs were in-order this made no difference, you just saved space (and decoder time).
However in OoO CPUs this causes a false dependency, and that is what you would observe on the Pentium Pro, where the optimisation manuals would recommend MOV. Recognising the issues this could pose to legacy software (and the unnecessary impact on binary sizes), Intel special-cased xor R, R in the PII and every OoO CPU since.
Modern CPUs (since SB for intel) go even further, as xor R, R is handled in the register renamer and not even forwarded for execution.
The Pentium Pro did optimize XOR reg, reg -- from an old Intel Optimization Guide:
Pentium Pro and Pentium II processors provide special support to XOR a register with itself,
recognizing that clearing a register does not depend on the old value of the register. Additionally, special support is provided for the above specific code sequence to avoid the partial stall. (See Section 3.9 for more information.)
And as long as x86 CPUs were in-order this made no difference
xor affects flags, mov does not.
Not that it matters much: compilers won't generate a conditional jump after such a xor, as since the zeroing always sets the flags the same, it would be effectively unconditional.
I remember seeing the assembly code for a BBC computer game that used XOR patterns to both remove and advance alien sprites, it was clever, the XOR removed the left edge and redrew the full sprite with new right edge moved over. The guy had pre-calculated the XOR patterns. It used more RAM but it saved a LOT of processing time.
I had a system where we kept a hash of giant sets of things using xor, because you can xor items into the hash when they’re added and xor them back out when they’re removed. So you don’t need to re-hash the whole set to maintain it.
XOR really is a fun operation. In my realm of teaching, I frequently show my students how XOR can be used as a controlled inverter in a physical circuit.
Yeah, XORs are really cool! Even though they're not that convenient compared to other bitwise operators, they're really useful, especially in recovering values. For example, they're used in Cuckoo Filters to get the bucket index. Long story short, Cuckoo Filter is an open-addressing hash table with 2 candidate buckets for each element. During a collision, it replaces the evicted element with its alternative bucket. But to find an alternative bucket, it uses XOR. https://maltsev.space/blog/010-cuckoo-filters#fingerprints-and-partial-key-cuckoo-hashing
Lots of symmetrical encryption algorithms make heavy use of XOR. They have tables of specially selected values that the data is XOR'd against, along with values values derived from the key. It scrambles the data very heavily, but is pretty efficiently undo-able due to the nature of the XOR operation.
Nerketur@reddit
Seeing this, I immediately thought of Quantum Mechanics.
X^V is like the superposition of X and V, but it acts more like entanglement. Given one of the values it immediately produces the other.
I wonder if there's a connection there, such that when you XOR with the observer, it produces the desired value. I may do a bit of research on my own about this.
ClysmiC@reddit
Given one of the values it immediately produces the other.
A clever but probably not very useful application of this is the XOR Linked List.
Honeytiger2010@reddit
Yeah! Look into CNOT gates. In gate based quantum computing, everything has to be reversible, but CNOT gates essentially are the same as XOR gates and are used to create entanglement. Whenever you have an operation that has a control of one or more qubits, it'll have the ability to potentially cause entanglement.
gimpwiz@reddit
My first "well that's weird" xor usage trick was the first time I read x86 assembly output. Instead of storing an immediate value of 0 into a reg, you would commonly instead see
xor r9 r9instead ofmov r9 0. People use xor in interesting ways from the very ground up.JeSuisOmbre@reddit
This is one of the most common idioms. Assembly optimizations are so neat
masklinn@reddit
What’s fun is it originated as a (officially recommended) space optimisation:
xor R, Ris two bytes whilemov R, 0is 5 (for 32b registers, for 64b it’s 3 and 7). And as long as CPUs were in-order this made no difference, you just saved space (and decoder time).However in OoO CPUs this causes a false dependency, and that is what you would observe on the Pentium Pro, where the optimisation manuals would recommend MOV. Recognising the issues this could pose to legacy software (and the unnecessary impact on binary sizes), Intel special-cased
xor R, Rin the PII and every OoO CPU since.Modern CPUs (since SB for intel) go even further, as
xor R, Ris handled in the register renamer and not even forwarded for execution.ack_error@reddit
The Pentium Pro did optimize
XOR reg, reg-- from an old Intel Optimization Guide:vytah@reddit
xoraffects flags,movdoes not.Not that it matters much: compilers won't generate a conditional jump after such a xor, as since the zeroing always sets the flags the same, it would be effectively unconditional.
Axman6@reddit
https://stackoverflow.com/a/33668295 has an extremely comprehensive explanation of the ins and out of different zeroing methods.
x86 also has a lot of NOP encodings, which can be useful for compilers to align code optimally: https://youtu.be/8BvAKvcW31A
Godd2@reddit
Except you can't actually do that, and all your examples are using a register, which is just memory.
gimpwiz@reddit
Are you sure?
bravopapa99@reddit
I remember seeing the assembly code for a BBC computer game that used XOR patterns to both remove and advance alien sprites, it was clever, the XOR removed the left edge and redrew the full sprite with new right edge moved over. The guy had pre-calculated the XOR patterns. It used more RAM but it saved a LOT of processing time.
Cannot recall the name! Long time passed.
redbo@reddit
I had a system where we kept a hash of giant sets of things using xor, because you can xor items into the hash when they’re added and xor them back out when they’re removed. So you don’t need to re-hash the whole set to maintain it.
cal_01@reddit
XOR really is a fun operation. In my realm of teaching, I frequently show my students how XOR can be used as a controlled inverter in a physical circuit.
axel-user@reddit
Yeah, XORs are really cool! Even though they're not that convenient compared to other bitwise operators, they're really useful, especially in recovering values. For example, they're used in Cuckoo Filters to get the bucket index. Long story short, Cuckoo Filter is an open-addressing hash table with 2 candidate buckets for each element. During a collision, it replaces the evicted element with its alternative bucket. But to find an alternative bucket, it uses XOR. https://maltsev.space/blog/010-cuckoo-filters#fingerprints-and-partial-key-cuckoo-hashing
Dean_Roddey@reddit
And of course a fundamental aspect of cryptography.
axel-user@reddit
Btw yeah, I'm not that deep into crypto implementation, but saw it can be used as symmetric encryption like
cipher_text = plain_text ^ secret;Dean_Roddey@reddit
Lots of symmetrical encryption algorithms make heavy use of XOR. They have tables of specially selected values that the data is XOR'd against, along with values values derived from the key. It scrambles the data very heavily, but is pretty efficiently undo-able due to the nature of the XOR operation.
Axman6@reddit
https://stackoverflow.com/a/33668295 has an extremely comprehensive explanation of the ins and out of different zeroing methods.
x86 also has a lot of NOP encodings, which can be useful for compilers to align code optimally: https://youtu.be/8BvAKvcW31A
dominikwilkowski@reddit
This is a great article! Well done.