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.
@rastersoft2 жыл бұрын
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).
@loonathefoxgirl63752 жыл бұрын
Ok thats pretty cool. I didn't know that. I kinda want to try implementing this some time
@rastersoft2 жыл бұрын
@@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...
@loonathefoxgirl63752 жыл бұрын
@@rastersoft i want to try it as an exercise. It would be interesting
@rastersoft2 жыл бұрын
@@loonathefoxgirl6375 oh,ok. Sorry then. I misunderstood you.
@loonathefoxgirl63752 жыл бұрын
@@rastersoft its ok. I forgot to clarify as a challenge to myself
@georgecop95382 жыл бұрын
Xor is used in encryption for its properties. For example: if A xor B = C then C xor B = A.
@HansBezemer2 жыл бұрын
.. or checksums. The ZX Spectrum loading routine used this.
@rexjuggler192 жыл бұрын
That was quite a "bit" of fun.
@JacobSorber2 жыл бұрын
😂
@YilmazDurmaz2 жыл бұрын
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
@sixtentamleht8153 Жыл бұрын
love that answear
@HansBezemer2 жыл бұрын
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.
@caesar1042 жыл бұрын
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.
@commitgit58892 жыл бұрын
Any modern compiler will optimize both multiplication by 0.5 and division by 2 with bit shifting.
@caesar1042 жыл бұрын
@@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.)
@Nick-lx4fo2 жыл бұрын
@@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
@skilz80982 жыл бұрын
@@commitgit5889 Yes, but that also depends on the compiler flags for the optimization levels...
@skilz80982 жыл бұрын
@@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.
@fordfactor2 жыл бұрын
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.
@cgln87602 жыл бұрын
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.
@unclerojelio63202 жыл бұрын
XOR is used for Linear Feedback Shift Registers as well.
@elclippo41822 жыл бұрын
XOR is the friend of every encryption algorithm.
@obeid_s2 жыл бұрын
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.
@sivaramd56372 жыл бұрын
We also swap them using sub and add operator instead of xor: x = x - y; y = y + x; x = y - x;
@henrykkaufman14882 жыл бұрын
Yes this is clever too, but it has one disadvantage - unlike XOR, it can overflow.
@sivaramd56372 жыл бұрын
Yes, the overflow problem exist
@spark_coder2 жыл бұрын
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 ...
@monochromeart73112 жыл бұрын
The issue with this beginner friendly method is that it's not overflow proof.
@spark_coder2 жыл бұрын
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.
@69k_gold Жыл бұрын
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
@zxuiji2 жыл бұрын
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.
@JacobSorber2 жыл бұрын
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.
@IamTheHolypumpkin2 жыл бұрын
I learned to understand binary operators and boolean algebra by playing around with minecraft redstone.
@trentlangford90502 жыл бұрын
The fact that XOR is essentially its own mathematical inverse is very interesting and very useful. This was an interesting video!
@Nyall Жыл бұрын
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
@AlexJacksonSmith2 жыл бұрын
This is like a one-time-pad logic to move values...
@SouravTechLabs Жыл бұрын
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.
@Uerdue2 жыл бұрын
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.)
@maxaafbackname55622 жыл бұрын
Very nice. That could be afor example done with a struct.
@mohammedsamir51422 жыл бұрын
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.
@angelcaru Жыл бұрын
There are three types of people: flag = !flag; flag = 1 - flag; flag ^= 1;
@KTegoshi2 жыл бұрын
oh fascinating. i only know of the address swap technique to do this
@PrateekJayaswal5 ай бұрын
/** 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
@unperrier59982 жыл бұрын
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.
@godnyx1172 жыл бұрын
Risc-v also has the first register (called literally "zero") to always be 0 no matter what you assign to it.
@unperrier59982 жыл бұрын
@@godnyx117 copycats! 😄
@godnyx1172 жыл бұрын
@@unperrier5998 LMAO!!!
@lorensims48462 жыл бұрын
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."
@redcrafterlppa3032 жыл бұрын
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
@rogo73302 жыл бұрын
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)
@FelixNielsen Жыл бұрын
That was some rather limited XOR fun. I had high hopes, as I m a sucker for bit twiddling, so more please.
@makealemonade2 жыл бұрын
Careful there!! Check for the case when x == y, don’t do xor when x == y since it will make it zero.
@sverkeren2 жыл бұрын
It works for x == y as well. Zeroes are perfectly benign, don't worry. Unless you divide by them of course.
@Hauketal2 жыл бұрын
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))
@packediceisthebestminecraf9007 Жыл бұрын
you could also do: x += y; y = x - y; x -= y; using + or - you could run into an overflow though, unlike with xor
@samplesandtests Жыл бұрын
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.
@LettersAndNumbers300 Жыл бұрын
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?
@vatsalnaik152 жыл бұрын
Nice video as always Jacob.!
@smrtfasizmu61612 жыл бұрын
I don't know for others but I like the content about encryption such as the one that Ben Eater has made.
@jorionedwards2 жыл бұрын
Guessing the solution based off the tittle, I tried it out and went all "What is this black magic?"
@raj_c2 жыл бұрын
Hi when you will offer embedded system course
@giancarl0212 жыл бұрын
Another possibility is: x = x + y; y = x - y; x = x - y;
@mgx93832 жыл бұрын
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.
@steffenpo2 жыл бұрын
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...
@savansanghavi74652 жыл бұрын
Best channel on the KZbin Some cpp videos would be great if possible for u
@streakz6595 Жыл бұрын
The solution I found is pretty simple (and it doesn't involve bitwise operations): x -= y; y += x; x = -(x-y);
@pantherwolfbioz132 жыл бұрын
You can swap the variables using the arithmetic plus operator. No need for xor x = x + y; y = x - y; x = x - y;
@pantherwolfbioz132 жыл бұрын
I didn't even think about overflow... Nice to know that even that doesn't pose any problems 😂😂
@sverkeren2 жыл бұрын
@@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.
@driverdmz Жыл бұрын
@@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.
@makealemonade2 жыл бұрын
Careful there! Check for the case when x == y, don’t do xor when x == y since it will make it 0.
@Mnogojazyk2 жыл бұрын
Well, I like it but I can’t admit to understanding it.
@rainfallen10642 жыл бұрын
Is there performance benefits to this?
@ohwow20742 жыл бұрын
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.
@EvilSapphireR2 жыл бұрын
@@ohwow2074 Modern x64 compilers will just use the xchg instruction anyways
@kaushaljani67692 жыл бұрын
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
@DenisovichDev2 жыл бұрын
Jacob, what a coincidence. I was literally thinking about checking XOR in C
I do think it would take fewer asm instructions with xor, but I'm not sure....
@EvilSapphireR2 жыл бұрын
He literally said not to call any other function
@rexsoltera2 жыл бұрын
@@EvilSapphireR Yeah, I know, but that's beside the point.
@EvilSapphireR2 жыл бұрын
@@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.
@danilomitrovic39542 жыл бұрын
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 🤷
@rterry126 Жыл бұрын
Python can swap using single line tuple assignment: x, y = y, x
@danilomitrovic3954 Жыл бұрын
@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.
@truefalse70592 жыл бұрын
found new way to swap two number
@justwatching61182 жыл бұрын
Cool! :)
@user-he4ef9br7z2 жыл бұрын
Jacob Xorber. ^=^
@zxuiji2 жыл бұрын
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
@billowen32852 жыл бұрын
Will people look at me strangely if I say ‘Zor’? It just seems more natural
@JacobSorber2 жыл бұрын
Maybe. 😏
@vk3fbab2 жыл бұрын
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.
@@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?
@EvilSapphireR2 жыл бұрын
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.
@AnyVideo9992 жыл бұрын
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.
@kz_cbble96702 жыл бұрын
X=x+y Y=x-y X=x-y
@TheJobCompany2 жыл бұрын
^
@youssefamen68722 жыл бұрын
^^
@Dje43212 жыл бұрын
^^^
@MrSRIVATSABR2 жыл бұрын
y = ((x ^ y) ^ (x = y)); Hey Jacob, I tried something like this and it works ! :)
@JacobSorber2 жыл бұрын
I have such a love hate relationship with that line of code. 😂 Thanks. I definitely needed that today.
@JacobSorber2 жыл бұрын
And, I should point out that while it probably will always work, it's not guaranteed to, since ^ is unsequenced.
@MrSRIVATSABR2 жыл бұрын
Haha, thank you !
@MrSRIVATSABR2 жыл бұрын
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.
@JacobSorber2 жыл бұрын
Correct. The order typically goes from left to right, but it's not guaranteed to.