An Interesting Trick with XOR to Flip Bits in a Byte!

As a programmer it won't be long before you need to start working with bits. Reading a certain bit. Setting a bit. And toggling a bit. Did you know you can swap the vale of two variables just using XOR? Here is how to do it all!

---

#garyexplains

[johngrwf]

Takes me back to my training at Arborfield Garrison 40 years ago. Subsequently, used for many years developing industrial robots for the pick & place industry.
Great video, many thanks. J

[MrWaalkman]

XOR is just an ADD without the carry.

So General Motors used a McAfee or a Norton program (I forget which) that would expand a .ZIP or a .7z file that was being copied to a jump drive and scan its contents to determine if the ZIP file contained any sensitive data. This effectively limited the throughput of a copy routine to roughly 1GB per day. Kinda slow...

After quite a bit of poking around, I found the the program looked at just the first two bytes of the file to determine what kind of file it was. If it started out with "PK", then it was a ZIP file. If it started out with "7z", then it was a 7Zip file.

So I created a program that XOR'ed the first two characters of a file with my favorite number, 69, and stored them back to the file and saved it. The protection routine would not detect the nature of the file because the signature was changed and thus allowed the file to be copied to the removable media directly. Running the program a second time returned it to its original contents.

The exploit has been fixed (I wasn't trying to hide what I was doing, and I went as far as to share it with IT), so consider either XOR'ing the entire file, or do the sensible thing and avoid working for GM altogether.

[ravimali]

This is nice refresher for advanced programmer 😛

[absurdengineering]

The “swap two variables without a temporary” trick is a real killer on RISC, since every pointer dereference will involve loads or stores, whereas registers are free and plentiful. This trick was nice on register-starved CISC CPUs that had the instructions that could do all this work with compact code. It wasn’t even about speed - but about keeping the code small since code space in a 16-bit-address systems was at a premium.

Today, compilers can optimize the trick away to a swap using a temporary variable, since that is less core and performs better, making the trick more of a bad habit.

It definitely takes understanding of the micro architecture and code generation capabilities of one’s compiler to depend on such tricks. Modern C and C++ compilers generate code that behaves as if it had the same behavior as the code you wrote. It doesn’t need to follow your every bit of high level code exactly. It just has to work the same since that’s what the standards demand, and “working the same” is defined there. Usually with the phrase “behaves as-if”.

[paulmichaelfreedman]

I'd rather flip burgers on a BBQ but it's winter and I'll settle for this.

[seancondon]

Oh good. You mentioned RAID. You know, it took me a while to understand how a RAID5 array could retain all the data if any one drive was missing. But once I understood how XOR worked, I had it figured out.

[kentkvalnes]

Nice bit flipping! Back to school again 🙂

[muddyexport]

And another good 101 class on bit magic!

[consumer]

Nice bitflip technique, the codebase at work actually uses if conditions for it lol

[maurizioferreira]

Using a single 'and' and a single 'xor', you can also do :

Set some bit
Reset other bits
Invert other bits,
Leave other bits unchanged.

Suppose you that you want to (counting from left to right) :

- invert bits 1 and 2
- leave bit 3 unchanged
- set bit 4 and 5
- invert bit 6
- leave bit 7 unchanged
- reset bit 8

How can you do that using just two operations ?
simply 'and' the byte with the following value
11100110
(this resets bits 4, 5, 8, leaving the others unchanged),
and xor the result with the following value:
11011100
This inverts bits 1, 2
than it leaves unchanged bit 3
bit 4 and 5, that were cleared by the 'and', are now set
bit 6 is inverted by the xor
bit 7 is left unchanged
bit 8, that was cleared by the 'and', is left reset.

[paulmichaelfreedman]

In Python, swapping values has been made very easy:

a, b = b, a

Done.
But the underlying function probably uses the method Gary describes.

[bayzed]

Why use XOR to flip bits when the NOT operator does the same thing?

[TheUnofficialMaker]

very interesting, thanks Gary. Don't see code in repository.