Комментарии:
x ^= y;
y ^= x;
x ^= y;
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 ...
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.
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.
asm ("xchg %0, %1;" : "+r"(x), "+r"(y));
Ответить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...
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."
ОтветитьI learned to understand binary operators and boolean algebra by playing around with minecraft redstone.
Ответить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.
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.)
Well, I like it but I can’t admit to understanding it.
ОтветитьPre-answer (before finishing video):
X=&y
*X
Y=&x
*Y
Interesting timing!
Before I knew it was "hashing", I sought to improve a loop whose purpose was to translate (English) month names to integers. ( "December" -> 12 ) Turns out adding the 2nd & 3rd letter of each month 'hashes' to unique values that could ( & 0x1F ) index into a 32 byte translation table.
Recently mucking with improving that, I discovered 12 unique values could result from a different hash function involving XOR.
Here's my gift to the world:
int monthOrd( char cp[ ] ) {
return "EA@BIC@KJ@DHGF@L"[ ((cp[0]<<1) + (cp[1]+1) ^ (cp[2]>>1)) & 0xF ] - '@';
}
Give it a string like "September" or "Oct" and it will give you the month's ordinal (with a lot of false positives!) Now that the caller knows which month (1-12), the caller can test the input is a valid name of a specific month (ie: not "Octopus"). A lot faster than making up-to 12 guesses with strcmp(). (And, yes, this is case insensitive... "JAN" or "January" or "jan" all return '1' .)
(The application of this is a lot more specific than De Bruijn's algorithm, but it's been a fun coding challenge to write the program that attempts various hashing functions searching for one that gives the desired results (12 unique hashes in a range of 0-15)...)
Cheers!
The fact that XOR is essentially its own mathematical inverse is very interesting and very useful. This was an interesting video!
Ответить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
Cool! :)
ОтветитьI don't know for others but I like the content about encryption such as the one that Ben Eater has made.
ОтветитьXOR is the friend of every encryption algorithm.
Ответить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)
If you want to know more about the XOR operator, just look at the XOR Truth Table within Boolean Algebra, then check out the how an actual XOR Gate works within a circuit. Then any functions that use bitwise logical operators such as ^, will become much more clearer to what is happening within the function and why XOR is being used. It is simple to understand, it is fast and cheap. These types of operators typically work at the register level unless they have to fetch the values from either cache, ram or some other memory device. I'm 100% self taught, and from my own personal learning experience is that if you can not understand XOR then why are you even writing source code or programming in the first place? All it is is bit manipulation through bit comparison.
Here's a couple of tables to make things simple:
XOR Truth Table:
A | B | O
------------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
==========================
Swapping Two Values:
Integer Value | 8 Bit or 1 Byte Binary Representation
A = 5 0000 0101
B = 12 0000 1100
==========================
A ^= B (A) 0000 0101 (5)
(B) 0000 1100 (12)
-----------------
A --> (9) (A) 0000 1001 (9)
---------------------------------------------------
B ^= A (B) 0000 1100 (12)
(A) 0000 1001 (9)
-----------------
B --> (5) (B) 0000 0101 (5)
---------------------------------------------------
A ^= B (A) 0000 1001 (9)
(B) 0000 0101 (5)
-----------------
A --> (12) (A) 0000 1100 (12)
==========================
A = 12
B = 5
However this only works on integral types such as int, signed, unsigned, bool, char. To swap floating point values a temporary in most cases must be used due to how floating point values are stored in memory.
XOR is a powerful tool and should never be frowned upon just cause the syntax might look confusing. Learn the instruction set, its functionalities and capabilities before trying to programming a device!
I have no formal education but I've been an independent study and hobbyist who's used C,C++,C# and a couple of other languages were my interests are within 3D Graphics Engine Design, Physics Simulation, Audio Processing, Animation, Hardware Emulation, and more. There is nothing wrong with the use of XOR!!!
This is my own opinion from my own experiences. I don't shy away from the use of bitwise logic or arithmetic operators where others may call it bit twiddling or bit hacking...
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.
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
Ответить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.
ОтветитьWill people look at me strangely if I say ‘Zor’? It just seems more natural
ОтветитьHi when you will offer embedded system course
Ответить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.
ОтветитьCareful there! Check for the case when x == y, don’t do xor when x == y since it will make it 0.
ОтветитьCareful there!! Check for the case when x == y, don’t do xor when x == y since it will make it zero.
ОтветитьThis is like a one-time-pad logic to move values...
ОтветитьXOR is used for Linear Feedback Shift Registers as well.
Ответитьoh fascinating. i only know of the address swap technique to do this
Ответитьy = ((x ^ y) ^ (x = y)); Hey Jacob, I tried something like this and it works ! :)
ОтветитьWe also swap them using sub and add operator instead of xor:
x = x - y;
y = y + x;
x = y - x;
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.
Ответить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.
Ответить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.
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 🤷
ОтветитьX=x+y
Y=x-y
X=x-y
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
That was some rather limited XOR fun. I had high hopes, as I
m a sucker for bit twiddling, so more please.
gawd. chaining assignments, x ^= y ^= x ^= y;
Ответить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
// (x ^ y) ^ y = x
// (x ^ y) ^ x = y
x ^= y; // x = (x ^ y)
y ^= x; // y = x
x ^= y; // x = y
The solution I found is pretty simple (and it doesn't involve bitwise operations):
x -= y;
y += x;
x = -(x-y);
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
Ответить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.
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?
Ответить