Having Fun with XOR (exclusive-or)
Vložit
- čas přidán 15. 06. 2024
- Patreon ➤ / jacobsorber
Courses ➤ jacobsorber.thinkific.com
Website ➤ www.jacobsorber.com
---
Having Fun with XOR (exclusive-or) // XOR is one of those things that new programmers either don't know about or wish they didn't know about, but it can do some really cool things. In this video, I want to show you one of them.
***
Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.
About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.
More about me and what I do:
www.jacobsorber.com
people.cs.clemson.edu/~jsorber/
persist.cs.clemson.edu/
To Support the Channel:
+ like, subscribe, spread the word
+ contribute via Patreon --- [ / jacobsorber ]
Source code is also available to Patreon supporters. --- [jsorber-youtube-source.heroku...]
For me it's easier to think about this like so:
on the second row you have "y == b xor (a xor b)". Since xor is commutative and associative you can rewrite that as "a xor (b xor b)".
Since (a xor 0 = a) and (a xor a) = 0 you get "a xor 0" -> a.
Xor is used in encryption for its properties. For example: if A xor B = C then C xor B = A.
.. or checksums. The ZX Spectrum loading routine used this.
The Z88 computer used XOR to have double-linked lists but using a single pointer instead of two: it stored the XOR of the previous and next blocks addresses, so you needed the addresses of two consecutive blocks to be able to move along it (of course, with the first or the last block it wasn't a problem because an address XOR null is the address itself).
Ok thats pretty cool. I didn't know that. I kinda want to try implementing this some time
@@loonathefoxgirl6375 well, that made sense in the Z88 because it was an 8bit computer with only 32kbytes of RAM. In a modern computer it doesn't make sense to do that, only as an exercise...
@@rastersoft i want to try it as an exercise. It would be interesting
@@loonathefoxgirl6375 oh,ok. Sorry then. I misunderstood you.
@@rastersoft its ok. I forgot to clarify as a challenge to myself
That was quite a "bit" of fun.
😂
a XOR a sets ANY number to ZERO. Very handy in Forth, where I defined this as : >ZERO DUP XOR ; It beats a sequence like DROP 0, which requires you to compile a full literal number. In Z80 assembly (where I learned this), the opcode XOR A does the same as LD A, 0 but beats it on virtually every criterium.
I think you can make video about these operators. Also the price and efficiency of operators and functions (such as time and performance differences between multiplication with 0.5 and division with 2) might be good topics to mention too. Thank you for sharing your valuable knowledge with us.
Any modern compiler will optimize both multiplication by 0.5 and division by 2 with bit shifting.
@@commitgit5889 Yes you might be right(because I don't have enough information about what you said), but what I am trying to say is, there are other ways to perform an instruction and some of them are more optimized. And it is important to know which operators and functions take more time in the execution. Therefore, it is worth to mention. In some scenarios, using bitwise operators more reasonable than using multiplication or division. This knowledge is quite important while developing a new algorithm. Especially with restricted resources. I hope Jacob will create some time and enlight us about this topic :) (I am not a native speaker so please ignore my mistakes in the language.)
@@caesar104 Modern compilers will always optimize simple operations like so, it really comes down to whether you want your code to be readable or not
@@commitgit5889 Yes, but that also depends on the compiler flags for the optimization levels...
@@Nick-lx4fo If XOR is unreadable then I'd like to think your in the wrong industry... That's kind of like a math teacher not knowing what PI, e or i is.
I recall using XOR logic to implement a selection rectangle that highlights what you select when you click and drag your mouse pointer over an image. An XOR converts the image pixels to the rectangle colour, and then a subsequent XOR changes it back to the original colour if the selection rectangle changes.
there is another similar one (no temp) but with addition/subtraction, provided that the total will stay in the range:
x = x+y // x=a+b
y = x-y // y=a
x = x-y // x=b
love that answear
XOR is used for Linear Feedback Shift Registers as well.
Xor is used by disk controllers to recreate missing missing data in a RAID 5 array, in a raid array with 4 data disks and one parity disk, the parity disk is created by Xoring the data of the 4 data disks, then if any one disk fails (including the parity disk) the missing data is recreated by xoring the data on all remaining disks, this can be used in real time and also to rebuild the new disk that replaces the failed disk.
Although the XOR method would be faster (I believe) because it is a bitwise operation, this seems to be an easier to grasp solution for beginners
(although XOR is better for learning the fundamentals of computer science)
x = x + y; // x = (x + y)
y = x - y; // y = (x + y) - y = x (remember this for the next step)
x = x - y; // x = (x + y) - x = y
... TaDa ...
The issue with this beginner friendly method is that it's not overflow proof.
That is indeed true which is why I had mentioned that the XOR method is better for learning computer science and edge cases like this.
You say it saves memory but that's not true, not even in asm, you spend more memory on the instructions then simply adding a stack variable, in asm you don't even need to swap register values, you simply load into the registers the values normally then just write them into opposite destinations. Aside from those points I do at least see this an interesting usage.
Ah, good point. This seems to be my specific work creeping into things. Sorry if it causes any confusion. On the MCUs I work with mostly, we have FRAM and RAM. FRAM is where our code goes, and we have a lot more of it. RAM is typically where our variables go, and it's more scarce. Anyway, because our code memory is more abundant, we often "save" memory (RAM) while increasing FRAM usage. I definitely could have been more precise in the video.
It's important to remember that this only works on chars, long longs, longs, ints and shorts. IEEE-754 forbids XOR operation on floats and doubles
XOR is the friend of every encryption algorithm.
I learned to understand binary operators and boolean algebra by playing around with minecraft redstone.
In x86 assembly we used to use XOR to zero a register without having to incur a memory fetch.
More recent CPU have a way to zero a register, for example sparc has the zero register which is hardcoded to 0x0 inside the CPU logic.
Risc-v also has the first register (called literally "zero") to always be 0 no matter what you assign to it.
@@godnyx117 copycats! 😄
@@unperrier5998 LMAO!!!
Nice video as always Jacob.!
I love the bits (byte) and i dont have degree, so i had to learn the hard way, i decided to write webSocket so i can encode the message, i saw the frame, tried to understand it, and now i'm kinda 70% learned how to deal with bytes and charsets ..
BUT.. its the first time i know from you, that i can swap with XOR .. lol
So Thank you.. hope u hit 100K soon.
I used to do a lot of 68k assembly, which is a 32bit processor. Here's something I thought of to left shift a 64bit integer in two regisers d0, d1, by a value in d2. It destroys d3. Output is in d0 and d1
d3 = d1 // make a copy of the lower 32 bits into d3.
d0 = d0 shifted left by d2 // left shift the upper 32 bits, but moves in zeros for the LSBs.
d1 = d1 shifted left by d2 // left shift the lower 32 bits.
d3 = d3 rotated left by d2 // rotate the lower 32 bits
d0 = d0 xor d3 // fill in the LSBs of the upper 32 bits of the result, but this modifies the MSBs of the upper 32 bits.
d0 = d0 xor d1 // un-modify the MSBs
The fact that XOR is essentially its own mathematical inverse is very interesting and very useful. This was an interesting video!
Assuming x and y are 32-bit integers, placed immediately next to each other in memory, with y having the lower address:
asm ("rolq $32, %0;" : "+m"(y));
(Interprets x and y as one 64-bit number and rotates that by 32 bit, i.e. shifts it 32 bit to the left with those bits that would be shifted out on the left being shifted back in on the right.)
Very nice.
That could be afor example done with a struct.
We also swap them using sub and add operator instead of xor:
x = x - y;
y = y + x;
x = y - x;
Yes this is clever too, but it has one disadvantage - unlike XOR, it can overflow.
Yes, the overflow problem exist
This is like a one-time-pad logic to move values...
oh fascinating. i only know of the address swap technique to do this
Do you know what sizes the t-shirts at merchonate are? Is there an American standard for s, m, l...? I'm from Europe and here every shop usually has their own measuring chart. Thanks in advance
Another possibility is:
x = x + y;
y = x - y;
x = x - y;
That was some rather limited XOR fun. I had high hopes, as I
m a sucker for bit twiddling, so more please.
i wonder if it can be done in assembly (on some processor) to swap the values in registers, without using any ram. i don't think it can be done in x86 assembly and i don't think 6502 assembly has a xor opcode.
Unfortunately throughout my entire programming career, I never had to swap two variables :( Maybe I am unlucky...
But - I use XOR for one thing for sure, and it's handy. Consider this:
i = 0
# toggle some flags to true - false or 0 - 1
i = i == 0 ? 1 : 0
This toggles i every time. Say you want to toggle light on an off with an Arduino or something like that.
Now the whole thing can be just replaced with:
i = 0
i ^= 1
This is the thing I need a lot, like a lot of times. And there are other usages too. I knew the variable swap stuff, but just never needed it. It's good for cryptographical stuff mostly.
Hi when you will offer embedded system course
My fav Google interview question: you have an array of integers where every number in it occurs an even number of times except for one number. What is the optimal way to find it?
Use xor to toggle a flag instead of using if statements or even the ternary operator.
bool flag = 1;
flag ^= 1; // toggle between true and false
Bonus: we can also use addition + and subtraction - to swap x and y.
There are three types of people:
flag = !flag;
flag = 1 - flag;
flag ^= 1;
Boah... well, even for me as an IT and elecronitc guy for many years... Well, i knew what XOR is used for an i did use it alot for stuff like digital input signal changes detection and stuff but i never ever thought about using it to swap integer values around.
Well if i think about it with some C type casting it is possible to swap pointers and floats around...
Cool! :)
Careful there!! Check for the case when x == y, don’t do xor when x == y since it will make it zero.
It works for x == y as well. Zeroes are perfectly benign, don't worry. Unless you divide by them of course.
Every time I see this I think about a comic (strip?) I saw in the early eighties rthat referenced a (tech) wizard with the name of "Exorandandor."
Works the same if you use minus instead of xor. But needs unsigned operands to avoid undefined behaviour.
x -= (unsigned y); and so on.
Also xor may be simulated with the other bit operations:
#define xor(x,y) ((x)^(y))
or
#define xor(x,y) ((x)&~(y)|~(x)&(y))
you could also do:
x += y;
y = x - y;
x -= y;
using + or - you could run into an overflow though, unlike with xor
I don't know for others but I like the content about encryption such as the one that Ben Eater has made.
Jacob, what a coincidence. I was literally thinking about checking XOR in C
Best channel on the CZcams
Some cpp videos would be great if possible for u
/**
XOR is a bit operation.
It accepts two operands and compares their values.
XOR evaluates to 0(False) if the operands are the same.
If they differ, it outputs outputs 1(True).
Here's its truth table:
x y (x^y)
1 1 0
1 0 1
0 1 1
0 0 0
i.e. x^y has the memory to remember if x and y were the same bit or not
Properties:
Its commutative so x^y == y^x,
Its associative so x^(y^z) == y^(x^z) == z^(y^x),
Its neutral element is zero so x^0 == x,
Its self annihilating so x^x == 0
Property used for swapping:
let x = (1)2 & y = (1)2
x ^ y = (1 ^ 1)2 = (0)2
Jacob Xorber. ^=^
I once come up with xor-swap for myself when i remembered that basically we can via xor put numbers on each over and then remove them out of this mess. I was even proud of myself, lol)
(A, B); (A^B, B); (A^B, A^B^B) = (A^B, A); (A^B^A, A) = (B, A)
Guessing the solution based off the tittle, I tried it out and went all "What is this black magic?"
Is there performance benefits to this?
No. Modern compilers do this stuff at -O2 level of optimization. So that you don't have to pollute your code like this. Just use the temp variable version.
@@ohwow2074 Modern x64 compilers will just use the xchg instruction anyways
Careful there! Check for the case when x == y, don’t do xor when x == y since it will make it 0.
The solution I found is pretty simple (and it doesn't involve bitwise operations):
x -= y;
y += x;
x = -(x-y);
You can swap the variables using the arithmetic plus operator. No need for xor
x = x + y;
y = x - y;
x = x - y;
I didn't even think about overflow... Nice to know that even that doesn't pose any problems 😂😂
@@driverdmz 8 will overflow to -8 in your 3-bit example. So it works for two's complement. The problem is the C standard does not guarantee two's complement, and overflow of signed inters are therefor undefined behavior.
@@sverkeren You're right. It was a poor example. The point should have been XOR won't rely on an underflow and overflow to fumble into a correct answer.
If sum of value does not exceeds limit
Then
X=x+y
Y=x-y. // It becomes x
X=x-y // x+y - x hence y
Well, I like it but I can’t admit to understanding it.
found new way to swap two number
void swap(int* const x, int* const y)
{
*x += *y;
*y = *x - *y;
*x -= *y;
}
Hope it's not unreadable!
I do think it would take fewer asm instructions with xor, but I'm not sure....
He literally said not to call any other function
@@EvilSapphireR Yeah, I know, but that's beside the point.
@@rexsoltera how can the problem statement be beside the point? If the problem wasn't stated in such a way there are much better ways to swap variables (mainly just to use a third placeholder variable and that's it). If you were just going for less instructions, it would not take less instructions than xor because there of course would be function calling asm instructions overhead.
This is what I came up with on paper:
x = x NXOR y
y = x NXOR y
x = x NXOR y
But I guess there's a simpler way.
Edit: Well, negation is unnecessary.
I remember years ago struggling with a SQL query. It looked simple but I couldn't get it to give the correct results. Ended up making a truth table and it ended up being XOR. So wrote XOR into my query and it passed all of the tests. Probably not efficient and had lots of comments explaining what was going on.
b4 I continue watching I'll just mention that the AND op is also useful for skipping bit checks, for example in a bignum function I use for mimicking the XOR op for not necessarily aligned bit bignum integers (like sub sections of larger integers, like the exponent of FPNs, that was a real wall to overcome for bignum math), instead of
if ( a.bit & A->data[a.byte] )
{
if ( b.bit & B->data[b.byte] )
B->data[b.byte] ^= b.bit
}
I would have something like:
bit = (B->data[b.byte] & b.bit) * !(a.bit & A->data[a.bit);
B->data[b.byte] &= ~(b.bit);
B->data[b.byte] &= bit;
May have mis-remembered my code but you get the idea, skip the jumps in favour of an extra instruction or 2, the cpu can just bulldose through instead of potentially stopping, reading a different set of instructions to what it pre-loaded and then continuing, for bignum math speed is more important than clarity in the code so even if it looks like a hack it does the job better than the clear version
To all, this doesn't work with python with negative numbers. Python works with specific format to represent negative numbers that uses XOR. Results may wary 🤷
Python can swap using single line tuple assignment: x, y = y, x
@rterry126 it can... but it can't swap with XOR gate. It displays correct numbers but it doesn't have same memory imprint. Thus this doesn't work.
Will people look at me strangely if I say ‘Zor’? It just seems more natural
Maybe. 😏
XOR is much better off though of as addition where 1 represents all odd numbers and zero represents all even numbers. Then everything becomes very intuitive from the rules of addition we are accustomed to.
x=x+y
y=x-y //y now holds the value of old x
x=x-y //x now holds the value of old y
Lol.
Pre-answer (before finishing video):
X=&y
*X
Y=&x
*Y
You forgot the dereferencing operator
@@EvilSapphireR thank you for your timely observation. Curious, do you know if there is a way to deference in bash?
Situation: a command sitting on the top of a named pipe, with a transformation buffer on the read end. And when I reference the buffer it's null, because I never actually get a copy of the data (because the write is to the lock: re-enforcing that it's shared memory).
Is this a limitation of bash?
X=x+y
Y=x-y
X=x-y
^^^
^
^^
y = ((x ^ y) ^ (x = y)); Hey Jacob, I tried something like this and it works ! :)
I have such a love hate relationship with that line of code. 😂 Thanks. I definitely needed that today.
And, I should point out that while it probably will always work, it's not guaranteed to, since ^ is unsequenced.
Haha, thank you !
Just to understand clearly, you're saying there might be a problem if (x = y) evaluates first and then (x ^ y) ? it is interesting to learn :) Thanks for your response.
Correct. The order typically goes from left to right, but it's not guaranteed to.
gawd. chaining assignments, x ^= y ^= x ^= y;