15 ms·

That XOR Trick (2020)

428 points by wagslane 6y ago

fh973 6y ago
Surprised this doesn't have my favorite XOR trick: implementing a double-linked list with one pointer! Store predecessor XOR successor in each node. I suspect this clicks already with everyone, and I don't need to explain forward and backward iteration.
- viraptor 6y ago
  What it doesn't click with is GC. Any pointer xor trick will fail when trying to add a GC to the app, because the pointers don't point at the right thing anymore.
  - saagarjha 6y ago
    GCs don't typically let you work with raw pointers.
ignoramous 6y ago
One of the coolest XOR tricks I've seen is fast encoding of negative integers to positive integers (unsigned) employed by ProtoBufs. It is called ZigZag encoding where negative and positive integers are interleaved such that lower negative values are assigned to lower positive values: input zz(int) 0 0 1 2 2 4 3 6 -1 1 -2 3 zz(n int64) => (n << 1) ^ (n >> 63) unzz(n int64) => (n >> 1) ^ (-(n & 0x1)) https://developers.google.com/protocol-buffers/docs/encoding?csw=1#types https://developers.google.com/protocol-buffers/docs/encoding... Edit: Fixed unzz, ref: https://github.com/lemire/FastIntegerCompression.js/blob/033768f72/FastIntegerCompression.js#L44-L46 https://github.com/lemire/FastIntegerCompression.js/blob/033...
- user-the-name 6y ago
  unzz does not look correct there. Edit: Looks good now!
- ufo 6y ago
  Doesn't a bitwise OR work just as well as a XOR here?
philihp 6y ago
A great disturbance in the force, as if millions of gatekeeping interviewer voices suddenly cried out in terror and were suddenly silenced.
tlb 6y ago
> XOR all values between 1 and n An O(n) algorithm!? You'd expect there to be a closed-form solution for this, analogous to summing a series using n*(n-1)/2. OEIS to the rescue. http://oeis.org/A077140 http://oeis.org/A077140 gives ((n+1)%2)*n + (n+(n%2))//2 % 2
- lifthrasiir 6y ago
  It was not super obvious to me, but the actual sequence is https://oeis.org/A003815 https://oeis.org/A003815 which is the absolute value of A077140. The entry for the latter gives another formula for A003815 however, which is distinct from a formula (1+3x-x^2+x^3)*x/(1-x^4)/(1-x^2) given in A003815.
- smlckz 6y ago
  (n+1)%2 = if (n+1) is divisible by 2 then 0 else 1 = (n+1) & 1 = ~(n & 1) ((n + (n % 2)) // 2) % 2 = ((n + (n & 1)) >> 1) & 1 = ((n & 2) >> 1) ^ (n & 1) = (n ^ (n >> 1)) & 1 In human terms, that means XOR of 1, 2, ..., n is: (if (n is divisible by 2) then n else 0) + (if ((if (n is divisible by 2) then n else n + 1) is divisible by 4) then 1 else 0) Or, as code: n * ~(n & 1) + (n ^ (n >> 1)) & 1 Phew! Can this be made any simpler or smaller? 1 ^ 10 = 11, 11 ^ 11 = 0, 0 ^ 100 = 100, 100 ^ 101 = 001, 1 ^ 110 = 111, 111 ^ 111 = 0, 0 ^ 1000 = 1000, ... ---- If you have some time, take a pen and a paper and think it through, you'll really like it...
  - Y_Y 6y ago
    This is a really neat result. I bet Euler or Gauss already thought of it and the solution is somewhere in a book full of such solutions.
  - kevinventullo 6y ago
    The simplest formula from the OEIS page seems to be a(4n)=4n, a(4n+1)=1, a(4n+2)=4n+3, a(4n+3)=0. Once you have the formula in front of you, it’s easy to prove it by induction. A branchless implementation of this function with no multiplies or divides: f(x)=(x^(x&1-1))+(((x+1)&2)>>1)
  - 6y ago
danpalmer 6y ago
As mentioned in this article, x ^ x == 0. Fun fact, this is frequently used by compilers as a "cheap" way to zero out a register. In addition, there are comparatively few cases in programming where we XOR. Sure, it happens in things like games quite a lot, but the main use is actually _cryptography_. Between these two facts (more like hints really), I managed to reverse engineer the bulk of a piece of malware I was given to analyse in a an internship. I was handed the malware, a copy of IDA Pro, and given a few days to see what I could find. All I could remember when presented with a wall of hex encoded machine code were the hints above. I looked for XORs of different values, assumed it was crypto, and extrapolated from there. Found a routine happening three times in quick succession and guessed it was triple-DES. Then I guessed that writing your own 3DES from scratch was unlikely, so googled for crypto libraries and happened to find one that nearly matched (I think an earlier/unmodified version), and worked my way up tagging the operations until I got to the purpose, exfiltrating various registry keys and browser history to [somewhere]. It was a fun exercise, and therefore these facts will stay with me for far longer than they are accurate I'm sure!
- gameswithgo 6y ago
  I feel like xor comes up all the time in programming! Perhaps generations that have almost entirely focuses on web front and backends never have use for it, but libraries underneath it all certainly are.
- toxik 6y ago
  A somewhat common use of XOR is p != q. It is actually an XOR. Another useful way to think of XOR is "either p or q is true, but not both, and not neither."
  - bonzini 6y ago
    Compilers can optimize "a != b" to "a xor b" if they know that both operands are 0 or 1. There are crazy many expression rewriting rules.
    - dan-robertson 6y ago
webel0 6y ago
I hope this article takes off so that my company will have to change its initial code screen. We make no use of xor in our rather large codebase (I’ve checked) yet pin a lot on whether an interviewee is aware of this trivia.
- whimsicalism 6y ago
  You have a single question that is always present in your "initial code screen"? XOR-only questions are poor unless you're interviewing someone for a very specific kind of role.
  - airstrike 6y ago
    > You have a single question that is your "initial code screen"? He never claimed that. It could just be part of the screen
    - whimsicalism 6y ago
      You're right and my question was poorly phrased. I meant: you have a single question that is asked as part of every single screen every year?
      - deathanatos 6y ago
        I'm not sure what you mean by "every year", but when I screen candidates, yes, I'll ask multiple candidates the same question? It allows me to compare candidates directly without introducing the additional variable of wondering whether one had a harder question, it allows me to gain & retain experience at asking the question in how it is presented, and if the candidate does well, how we proceed to make it more difficult to suss out the candidate's skill. I do agree with the parent above though that this use of xor is trivia, and not a great interview question.
  - webel0 6y ago
    One of several. But I agree with the general sentiment.
yotamoron 6y ago
I would never work in a place that is asking such questions in the job interview.
diegocg 6y ago
The xor swap can be dangerous: if variables have the same value, they xor to zero so you end up losing the values of both variables.
- IgorPartola 6y ago
  So you do a check beforehand for whether you need to swap them at all?
- flohofwoe 6y ago
  It also works if both are equal since only one value will ever be zero: x=2, y=2: x^=y => x=0, y=2 y^=x => x=0, y=2 x^=y => x=2, y=2
- extropy 6y ago
  a = 5 b = 5 a = a ^ b = 0 b = a ^ b = 5 a = a ^ b = 5 You where saying?
- deleted 6y ago
  [deleted]
- tempodox 6y ago
  You are wrong. Just try it out yourself. TFA actually explains why it still works even in that case.
- deleted 6y ago
  [deleted]
- tlb 6y ago
  Not if they have just the same value, but if they're the same memory location. So check the pointers: void swap(T &x, T &y) { if (&x == &y) return; x ^= y; y ^= x; x ^= y; }
- user-the-name 6y ago
  You are confused about the problem here. It is not that both values are the same, it is you are applying the xor swap using pointers to values, and both pointers point to the same value in memory.
Straw 6y ago
You can actually extend the XOR trick for missing elements to any fixed number! The standard (non-XOR) low-memory solution calculates the sum of x, x^2, x^3, ..., x^n, which gives enough information to find the missing elements as the roots of an n degree polynomial. We can just do the same thing in the finite field F_{2^k}, where k is the bitwidth of the integers. Addition in this field corresponds to a bitwise XOR, so the first term gives exactly the 1-missing case! I don't remember how to actually solve the resulting polynomial over the finite field though.
- dandanua 6y ago
  Addition in F_{2^k} is not the same as XORing. But that summation idea is correct. To solve polynomial you can use this algorithm https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algo...
  - Straw 6y ago
    Oh, neat, what's the runtime? https://math.stackexchange.com/questions/1479745/relations-of-galois-field-to-bitoperators-in-c https://math.stackexchange.com/questions/1479745/relations-o... What have we missed?
    - dandanua 6y ago
      Ah, XORing is indeed addition in F_{2^k}. It's not addition in Z_{2^k}, though. I was thinking about summation modulo prime number, in this case Z_p = F_p.
j-pb 6y ago
Ah off by one errors are hard: > 1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 1] should be > 1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 2] Because a 0 indexed array of length n-1, has n-2 as it's last index. After all, it's missing a value.
- ml_giant 6y ago
  Let's try an example with n=4: 1 ^ 2 ^ 3 ^ 4 ^ A[0] ^ A[1] ^ A[2] ^ A[3] It might be early in the morning and I am missing something, but it has n-1 as its last index. Any insight is appreciated :) Edit: There is a missing number in the array, thus its last index is n-2. Thanks for the correction, OP.
  - bonzini 6y ago
    But there are only 3 items in the array (for example 1, 2 and 4). So the last valid index is 2.
    - ml_giant 6y ago
      Ah. I was about to make an edit to my comment as you are correct :) Thanks!
  - j-pb 6y ago
    Premise: A is containing all values in range [1, 4] except one: Let's say that, without loss of generality: > 1 ^ 2 ^ 3 ^ 4 ^ A[0]=1 ^ A[1]=2 ^ A[2]=3 ^ A[3]=4 However, A is now missing no value. Contradiction. ∎
- epsilon-greedy 6y ago
  Author here (Florian): I just fixed this. Very good catch. Off-by-one errors are hard indeed. :)
IgorPartola 6y ago
So this is how you’d solve the Fallout 3+ hacking challenges? :) In practice I cannot think of a time when I was confronted with this particular problem. Usually if I need to find a duplicate I have no guarantees that there isn’t more than one or if there is a duplicate at all. I don’t think I’ve ever had to practically solve the “every number but one” problem. Curious where such problems arise in the wild, except interview puzzles.
blauditore 6y ago
This is conceptually almost the same as summing over all entries and comparing to the sum of all numbers in [1, n], except that the latter can be done more efficiently because that sum is simply n*(n+1)/2. There are in fact legit use cases for XOR to speed things up or make algorithms simpler, but this is not the case here IMHO.
- abhishekjha 6y ago
  XOR handles overflow better than the summing mechanism.
wagslane 6y ago
I recently wrote an article explaining what makes XOR so special - may help put this in context: https://qvault.io/2020/01/18/why-is-exclusive-or-xor-important-in-cryptography/ https://qvault.io/2020/01/18/why-is-exclusive-or-xor-importa...
trinovantes 6y ago
Xor trick may reduce the time/space complexity of a solution but I'd say it definitely increases the cognitive load (maintenance) complexity. Outside of few niche industries/use cases, the increased developer cost will probably outweigh whatever extra hardware you'd need to compensate.
- cuspycode 6y ago
  Agreed, the XOR trick is just a clever trick that might be useful in some esoteric niche cases, but otherwise don't bother. GCC will even optimize away the XOR operations when this is used for simple things like ints on amd64. I did a simple compile test, and with -O1 and higher I got identical machine code for the XOR algorithm and the naive swapping version. Without optimization I did get the XOR instructions, but the number of machine instructions was longer than for the naive case, and the number of CPU registers used was the same.
exabrial 6y ago
> There are a whole bunch of popular interview questions As a very personal strong opinion, this makes me groan. I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). I'd rather know whether or not they are a pleasant person, are a team player, whether they have leadership aspirations, and take responsibility.
- jenwkejnwjkef 6y ago
  Nobody wants to see the XOR solutions. These questions are really basic and only filter out the non-programmers. Any decent programmer should be able to solve all of these without a problem.
  - dragontamer 6y ago
    I wouldn't say "nobody" wants to see the XOR-trick solution. Its just that those who DO care about it is asking about the general solution: Reed-Solomon codes, or maybe a more modern (harder to understand) variant: like LDPC or Tornado codes. Anyone who needs to recover *ONE* symbol from a data-stream with noise actually needs to recover two, three... four... symbols in the general case. One symbol of erasure recovery is the weakest-of-the-weakest of error correction codes. Its even weaker than the single-error-correction / double-error detection Hamming Code (discovered back in 1950s). XOR-trick is your "basic parity bit", and is the stuff taught to undergrads to wet your appetite for error correction codes (well... erasure correction in this case. Since XOR isn't strong enough to actually correct an error. Only an erasure).
    - shiftingleft 6y ago
      I don't see how the problem corresponds to erasure coding. Typically in erasure coding you know the locations of the erasures. Here, you don't know the location. Maybe you can elaborate on how it relates to erasure coding?
durnygbur 6y ago
I swear this dude interviewed me once.
virgilp 6y ago
Slightly disappointed at the "two missing values" solution: First: one needs to realize that you can solve the "missing number" problem just as well with sums. So, if you're trying to find the "one missing number" between 1 and n, you simply subtract all values from n*(n+1)/2 (the sum of all said numbers) and you end up with the missing one. (using wrap-around semantics, you don't even need to have more bits of memory than you need for the xor solution!) Second: A common way to solve a problem with two variables is to build a system of two equations. One can compute, in a single pass, what is "a+b" and "a^b" ; solve the system, and you get both variables with no additional lookups. Now, it's true that if you get a carry from the addition, this problem might not be solvable...but, if you can afford one extra bit for the potential carry, you're all set.
- Strilanc 6y ago
  The xor, sum pair can't distinguish missing 11, 0 from missing 10, 1.
  - virgilp 6y ago
    Ah, you're right, I didn't think it through. It does feel like there must be a way to play with the bits so that you can retrieve it in a single pass, though - that'd be a much more interesting problem :). (of course, you can do it with sum + product, but that's going to be fairly expensive for large numbers)
- slymon99 6y ago
  Sums increase in size, however. The nice part of the xor trick is your xor result will be the size of the base of the numbers (64 bits or whatever). If you are reading several tb of 64 bit integers from disk that could get larger than your memory (though unlikely, probably why you see this in kernels where memory might be more of a concern especially with embedded)
all2 6y ago
A = { 1, 2, ... , k, ..., n-1, n}, for 1<=k<=n, and we're given integer n. sum({1..n}) = n(n-1) / 2 sum(A) = n(n-1) / 2 - k k = n(n-1) / 2 - sum(A) Is the interview question looking for a "clever" solution? I'm confused as to why someone would ask this question in an interview? It seems like the more challenging question would be "Find a method of summing a range 1..n in less than O(n) time/space complexity." [edit] I have a dumb. This calculation can happen in O(1). Because of n(n-1)/2, we know the sum of the range, no need to examine each value in the range. [/edit] Or, even more fun, limit the functions/instructions the interviewee can use (ex, some 4 or 5 instructions of x86/WASM/etc. machine instructions, max 1 or 2 registers, etc.) to complete the task.
- Vloeck 6y ago
  unless n equals 2^17 (or 2^33 if you calculate with longs)
okl 6y ago
For lot's of other fun bithacks, see: https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html
aljarry 6y ago
If you need XOR of two boolean values, you can just "z = x != y". That's my favorite XOR trick, as it's easily understandable and readable.
- abhishekjha 6y ago
  x!=y is itself calculated using XOR.
simias 6y ago
Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables always being a bit of a bother in C89) in my implementation I decided to implement the swap using the xor trick: s[i] ^= s[j]; s[j] ^= s[i]; s[i] ^= s[j]; I then ran a few basic test vectors, everything seems to work fine. A little while later I noticed that the output of the cypher was weird, the longer it ran the more zeroes I would get, eventually getting only zeroes. The keen reader will already have spotted the problem: whenever i and j happen to be equal instead of doing nothing the code sets the entry to 0 (since x ^ x == 0 for any x). And that's the story of how I never used this trick ever again. In general it's always better to write clear, concise code and let the compiler optimize it. If it turns that the code is performance critical and the compiler doesn't do a good enough job then you can see if the smart solution is worth it. And if you fail an interview because the interviewer expected you to know how to find a duplicate in an integer list by using xor then you probably dodged a bullet anyway. What a silly trivia question.
- deleted 6y ago
  [deleted]
- sleavey 6y ago
  I sometimes use your "bug" on purpose in tests, when checking that two values are either both defined or both undefined, but not one defined and one undefined: $ python >>> a, b = 1, 2 >>> bool(a) ^ bool(b) False >>> a, b = 1, 1 >>> bool(a) ^ bool(b) False >>> a, b = None, None >>> bool(a) ^ bool(b) False >>> a, b = None, 1 >>> bool(a) ^ bool(b) True (Note: this doesn't work if a value can be 0, because bool(0) is False in Python). This helps to avoid having to write something like `(a is not None and b is not None) or (a is None and b is None)`.
  - shiftingleft 6y ago
    Your note is very important, I think it would be good to give it more emphasis. What works flawlessly, however, is: In [1]: a = None In [2]: b = 0 In [3]: (a is None) ^ (b is None) Out[3]: True Alternatively, as suggested in another comment, you can use inequality as a replacement for XOR: In [4]: (a is None) != (b is None) Out[4]: True Another error prone pattern is the following: In [5]: a or b Out[5]: 0 Which can behave differently depending on the order of elements/values: In [6]: b or a Out[6]: None # should be 0 Since b is zero, it doesn't count. Less error prone, but also more verbose is: In [10]: a if a is not None else b Out[10]: 0
hyperman1 6y ago
A fun party trick not mentioned here is reducing storage in a doubly linked-ish list: Normally each node stores 2 pointers: struct Node {void * prev;void * next} The trick is to use only 1 'pointer', storing prev XOR next: struct Node {void* xored;} While traversing, you remember not only the current position, but also where you came from. So forward traversal goes: next= current.xored XOR previous. Backwards also works: Node * previous=(Node * )current.xored XOR (Node * ) next. The first and last node can use 0 as previous or next node, or you make a circular list. You do have to store a pointer to the first and last node, as usual. I've never seen this used in the real world, which is probably a good thing. It also plays hell with garbage collectors like Boehm, as they can't derive the 2 used adresses. UPDATE: And of course wikipedia knows everything: https://en.wikipedia.org/wiki/XOR_linked_list https://en.wikipedia.org/wiki/XOR_linked_list
- user-the-name 6y ago
  That is amazing and disgusting.
  - abhishekjha 6y ago
    I think there is something like this in linux kernel.
- jcmeyrignac 6y ago
  I used this trick in a sorting pancakes contest. Flipping a list of pancakes required only one XOR, whatever the size. Very nice trick.
- surajrmal 6y ago
  The bigger problem with this approach is that you can't remove/erase something from the list just by knowing it's address. This is a key mechanism for most use cases. However, if you're fine with limiting yourself to erasing only during iteration, it's pretty nifty. I've also done some benchmarks in the past and found it interior iteration performance due to what I'm assuming to be inability to prefetch the next address. However, linked list iteration is already relatively slow so I suppose it's not a big downside.
bjkchoy 6y ago
There is a very clever and beautiful algorithm that only uses the xor operation. It's the Luby Transform code, the simplest implementation of a Fountain Code. A Fountain Code lets you transmit a file over an unreliable connection (packets can be unordered, and even lost), with just a unidirectional communication. And this can be done just by xoring a random number of blocks from the file over and over! A very good explanation of the algorithm: http://blog.notdot.net/2012/01/Damn-Cool-Algorithms-Fountain-Codes http://blog.notdot.net/2012/01/Damn-Cool-Algorithms-Fountain...
jng 6y ago
I've known of XOR tricks since the 80s, when you would "undraw" a graphic on the screen by redrawing it with XOR. But only recently I learned that the implementation of multiport memory for CPU caches and the likes often uses a design based on multiple storage copies and XOR to get the last valid written result. Amazed that the CPU's cache is doing that kind of trick all the time just during regular code execution.
utopcell 6y ago
I'd been using xor swapping for years as x ^= y ^= x ^= y; until some point it occurred to me that this has undefined behavior in C.
- Aardwolf 6y ago
  That's one thing missing from BASIC in other programming languages, the SWAP statement: SWAP x y So few other languages have it, some languages even make it impossible to write a swap function by not supporting pass by reference or pointers. Python has something interesting except it requires typing the name of each variable twice
creeble 6y ago
Fun XOR trick: using it to move a cursor across the screen without having to keep a buffer of the contents under the cursor (and putting them back). It didn't always look great, but if you were moving a full-screen crosshair around, it was sufficient. Especially on hardware that was slow to move buffers to and from ram. Unfortunately, using this pure-math technique was also patented until 2007 [0], much to the surprise of my former employer in 1986. Cadtrak had collected from companies like IBM and NEC and made a nice business as a troll. [0] https://patents.google.com/patent/US4197590B1/en https://patents.google.com/patent/US4197590B1/en
- kbelder 6y ago
  Really? Apple ][ vector shapes had a XOR mode built in for non-destructively moving shapes across the screen, often used for cursors, and that was released in 1977.
aarchi 6y ago
Even better, store array A instead as a bit set, take the complement, then return the number of trailing zeros plus one.
c2xlZXB5Cg 6y ago
"Nim" game is also solved with XOR. https://en.wikipedia.org/wiki/Nim https://en.wikipedia.org/wiki/Nim
greggman3 6y ago
I've been asked this question before. I don't remember if I already knew the answer or not. But.... When does this ever come up in the real world. > You are given an array of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number. This has happened to me in real life exactly NEVER! I think maybe I was asked you have a list of pairs of integers except one number is missing its pair. Again, no idea where I would apply this in a real world situation.
- gnull 6y ago
  > This has happened to me in real life exactly NEVER! Do you do something applied like programming? I think problems (and solutions) similar to this one should be easy to find in TCS. The problem you quote seems valuable to me for its insight, it shows that you can reduce certain search problems to algebraic calculations which are easy to do. I think this is useful concept to understand, and a good mental exercise to try coming up with it yourself (even if you don't apply it directly). Could it be that even if you're a programmer who will never have to solve exactly this problem, you could still use the intuition you gain from this problem to solve others (or understand existing solutions you need to implement)? Could it be that you indirectly used the knowledge you have of this solution without being aware of it?
- physicles 6y ago
  I had a case today where I was comparing two sets for equality. If the range of values is large, you could xor everything together as a O(1) space check for likely equality. Result is nonzero -> sets definitely aren’t equal; result is zero -> sets are probably equal, but you’ll need to check again some other way to make sure. Of course this is absurd if you’re dealing with anything that already fits in ram, but it’s still neat to think about.
strenholme 6y ago
The thing about the “Use XOR to swap two variables” trick is that it’s a version of this solution which works for any two real numbers (or integers): a = a - b b = a + b a = b - a XOR is simply addition or subtraction modulo 2 for each bit, so making the above XOR looks like this: a = a ^ b b = a ^ b a = b ^ a
- volta87 6y ago
  The article touches on this, since its an important realization. In C, however, if the integers are not unsigned, the add/sub version exhibits UB on overflow, because C unnecessarily ties signed/unsignedness with overflow behavior (UB, two's complement, etc.). Not that this is important, but could hint why this trick is more often shown with XOR than with add/sub.
beeforpork 6y ago
Hmm, I would have used + and -, I suppose. The sum of 1..n is (n*(n+1))/2. Subtract from that all numbers in the array and what is left is the missing number.
- NieDzejkob 6y ago
  I suppose one downside of this approach is that you need a bigger datatype to contain the result.
  - beeforpork 6y ago
    No, not really, because you just need the lower half bits of the multiplication result, i.e., the size you need for your numbers. You do need to care about overflow: the /2 operation must not remove an upper bit from those lower bits. But you can easily do that before *: either n or n+1 is even. Divide the even number by two, then multiply by the odd one and keep only the lower bits. These lower bits are all you need, because the missing number is representable in it: subtracting may use wrap-around, but still, the remaining bits will be the missing number.
- marshmellman 6y ago
  It’s mentioned in the article that then you need to care about overflow.
crazydoggers 6y ago
My favorite trick is the XOR one time pad. XOR anything (text, images, etc) with a random pad or "key" the same length as the data your are encrypting... and you've got an completely unbreakable cipher. Just be careful as with any one-time-pad cipher. The key needs to be the same length as the data, generated randomly, and you can only use it once... no key reuse ever.
ynfnehf 6y ago
I have never gotten the point of this trick. Don't basically all processors have some equivalent of XCHG (swap contents of two registers)? Even the 8086 had it back in 1978. (The z80 doesn't have it, but it is a couple of years older than 8086.) I tried searching the LLVM source for any mention of the trick, but couldn't find anything. So I can't see it having any relevance to modern CPUs.
truepaurea 6y ago
This can also be seen as roots of matrices and is not exclusive to XOR, it can be done with addition and subtraction. I tried explaining it in [1]. [1]https://paureahack.blogspot.com/2016/04/swap-without-temporary-space.html https://paureahack.blogspot.com/2016/04/swap-without-tempora...
Const-me 6y ago
Good article, but this interview question is not good. > How to swap two numbers without using a temporary variable? I know interviewers expect XOR, but PCs have XCHG instruction. It’s the same error when they asking to compute number of set bits, expecting “lookup table”. Same error when they ask to find the least/most significant set bit index, expecting some bit tricks. Processors have dedicated instructions to do these things, typically faster than smart-ass manual versions. Moreover, for simple things like XCHG, BT, BTC, BSWAP compilers are aware and normally produce them from normally-looking i.e. readable code.
logbiscuitswave 6y ago
I’m a programmer by trade (and I like to think I’m pretty competent), but self-trained. Algorithms have always been a weakness of mine as a result of a lack of formal training. While I use XOR for some simple Boolean comparisons out of convenience, the kind of XOR use I see —- especially in crypto libraries has always been very mysterious to me. This article cleared up a lot of that for me. That being said, I often prefer readability over fancy so I don’t imagine using these tricks regularly but it’s nice to better understand how they work. This article did a great job demistifying this practice.
blt 6y ago
On a less clever note, I also find it useful to think about XOR as the "conditional inversion" operator: x invert? out 0 0 0 1 0 1 0 1 1 1 1 0 This has saved me some nested if-statements before.
seanwilson 6y ago
I've used XOR for undo/redo when I had limited memory in a painting app: - You have the canvas in state S before you draw on it and the canvas in state T after you draw on it. - Store (S XOR T). XOR this against T to undo back to S and XOR again to redo back to T. So if you want to have 10 levels of undo, you only need to store the final state and the 10 XOR diffs that got you there. The diffs will compress well too because most of the pixels on them will be blank (where nothing changed). All fairly easy to implement too e.g. compared to storing and replaying high-level commands to redo.
Fazel94 6y ago
> Arithmetic operators instead of XOR In that case, It uses Python that supports arbitrary long numbers out of the box so overflow of integers wouldn't be an issue(in Python3 default is arbitrary long integers).
sarcarx 6y ago
Note that the combined xor of the first n integers can be computed in constant time (oeis.org/A003815). a(4n)=4n, (4n+1)=1, a(4n+2)=4n+3, a(4n+3)=0

428 points by wagslane 6y ago

Surprised this doesn't have my favorite XOR trick: implementing a double-linked list with one pointer! Store predecessor XOR successor in each node. I suspect this clicks already with everyone, and I don't need to explain forward and backward iteration.

viraptor 6y ago
What it doesn't click with is GC. Any pointer xor trick will fail when trying to add a GC to the app, because the pointers don't point at the right thing anymore.
- saagarjha 6y ago
  GCs don't typically let you work with raw pointers.

ignoramous 6y ago

One of the coolest XOR tricks I've seen is fast encoding of negative integers to positive integers (unsigned) employed by ProtoBufs. It is called ZigZag encoding where negative and positive integers are interleaved such that lower negative values are assigned to lower positive values: input zz(int) 0 0 1 2 2 4 3 6 -1 1 -2 3 zz(n int64) => (n << 1) ^ (n >> 63) unzz(n int64) => (n >> 1) ^ (-(n & 0x1)) https://developers.google.com/protocol-buffers/docs/encoding?csw=1#types https://developers.google.com/protocol-buffers/docs/encoding... Edit: Fixed unzz, ref: https://github.com/lemire/FastIntegerCompression.js/blob/033768f72/FastIntegerCompression.js#L44-L46 https://github.com/lemire/FastIntegerCompression.js/blob/033...

user-the-name 6y ago
unzz does not look correct there. Edit: Looks good now!
ufo 6y ago
Doesn't a bitwise OR work just as well as a XOR here?

philihp 6y ago

A great disturbance in the force, as if millions of gatekeeping interviewer voices suddenly cried out in terror and were suddenly silenced.

tlb 6y ago

> XOR all values between 1 and n An O(n) algorithm!? You'd expect there to be a closed-form solution for this, analogous to summing a series using n*(n-1)/2. OEIS to the rescue. http://oeis.org/A077140 http://oeis.org/A077140 gives ((n+1)%2)*n + (n+(n%2))//2 % 2

lifthrasiir 6y ago
It was not super obvious to me, but the actual sequence is https://oeis.org/A003815 https://oeis.org/A003815 which is the absolute value of A077140. The entry for the latter gives another formula for A003815 however, which is distinct from a formula (1+3x-x^2+x^3)*x/(1-x^4)/(1-x^2) given in A003815.
smlckz 6y ago
(n+1)%2 = if (n+1) is divisible by 2 then 0 else 1 = (n+1) & 1 = ~(n & 1) ((n + (n % 2)) // 2) % 2 = ((n + (n & 1)) >> 1) & 1 = ((n & 2) >> 1) ^ (n & 1) = (n ^ (n >> 1)) & 1 In human terms, that means XOR of 1, 2, ..., n is: (if (n is divisible by 2) then n else 0) + (if ((if (n is divisible by 2) then n else n + 1) is divisible by 4) then 1 else 0) Or, as code: n * ~(n & 1) + (n ^ (n >> 1)) & 1 Phew! Can this be made any simpler or smaller? 1 ^ 10 = 11, 11 ^ 11 = 0, 0 ^ 100 = 100, 100 ^ 101 = 001, 1 ^ 110 = 111, 111 ^ 111 = 0, 0 ^ 1000 = 1000, ... ---- If you have some time, take a pen and a paper and think it through, you'll really like it...
- Y_Y 6y ago
  This is a really neat result. I bet Euler or Gauss already thought of it and the solution is somewhere in a book full of such solutions.
- kevinventullo 6y ago
  The simplest formula from the OEIS page seems to be a(4n)=4n, a(4n+1)=1, a(4n+2)=4n+3, a(4n+3)=0. Once you have the formula in front of you, it’s easy to prove it by induction. A branchless implementation of this function with no multiplies or divides: f(x)=(x^(x&1-1))+(((x+1)&2)>>1)
- 6y ago

danpalmer 6y ago

As mentioned in this article, x ^ x == 0. Fun fact, this is frequently used by compilers as a "cheap" way to zero out a register. In addition, there are comparatively few cases in programming where we XOR. Sure, it happens in things like games quite a lot, but the main use is actually _cryptography_. Between these two facts (more like hints really), I managed to reverse engineer the bulk of a piece of malware I was given to analyse in a an internship. I was handed the malware, a copy of IDA Pro, and given a few days to see what I could find. All I could remember when presented with a wall of hex encoded machine code were the hints above. I looked for XORs of different values, assumed it was crypto, and extrapolated from there. Found a routine happening three times in quick succession and guessed it was triple-DES. Then I guessed that writing your own 3DES from scratch was unlikely, so googled for crypto libraries and happened to find one that nearly matched (I think an earlier/unmodified version), and worked my way up tagging the operations until I got to the purpose, exfiltrating various registry keys and browser history to [somewhere]. It was a fun exercise, and therefore these facts will stay with me for far longer than they are accurate I'm sure!

gameswithgo 6y ago
I feel like xor comes up all the time in programming! Perhaps generations that have almost entirely focuses on web front and backends never have use for it, but libraries underneath it all certainly are.
toxik 6y ago
A somewhat common use of XOR is p != q. It is actually an XOR. Another useful way to think of XOR is "either p or q is true, but not both, and not neither."
- bonzini 6y ago
  Compilers can optimize "a != b" to "a xor b" if they know that both operands are 0 or 1. There are crazy many expression rewriting rules.
  - dan-robertson 6y ago

webel0 6y ago

I hope this article takes off so that my company will have to change its initial code screen. We make no use of xor in our rather large codebase (I’ve checked) yet pin a lot on whether an interviewee is aware of this trivia.

whimsicalism 6y ago
You have a single question that is always present in your "initial code screen"? XOR-only questions are poor unless you're interviewing someone for a very specific kind of role.
- airstrike 6y ago
  > You have a single question that is your "initial code screen"? He never claimed that. It could just be part of the screen
  - whimsicalism 6y ago
    You're right and my question was poorly phrased. I meant: you have a single question that is asked as part of every single screen every year?
    - deathanatos 6y ago
      I'm not sure what you mean by "every year", but when I screen candidates, yes, I'll ask multiple candidates the same question? It allows me to compare candidates directly without introducing the additional variable of wondering whether one had a harder question, it allows me to gain & retain experience at asking the question in how it is presented, and if the candidate does well, how we proceed to make it more difficult to suss out the candidate's skill. I do agree with the parent above though that this use of xor is trivia, and not a great interview question.
- webel0 6y ago
  One of several. But I agree with the general sentiment.

yotamoron 6y ago

I would never work in a place that is asking such questions in the job interview.

diegocg 6y ago

The xor swap can be dangerous: if variables have the same value, they xor to zero so you end up losing the values of both variables.

IgorPartola 6y ago
So you do a check beforehand for whether you need to swap them at all?
flohofwoe 6y ago
It also works if both are equal since only one value will ever be zero: x=2, y=2: x^=y => x=0, y=2 y^=x => x=0, y=2 x^=y => x=2, y=2
extropy 6y ago
a = 5 b = 5 a = a ^ b = 0 b = a ^ b = 5 a = a ^ b = 5 You where saying?
deleted 6y ago
[deleted]
tempodox 6y ago
You are wrong. Just try it out yourself. TFA actually explains why it still works even in that case.
deleted 6y ago
[deleted]
tlb 6y ago
Not if they have just the same value, but if they're the same memory location. So check the pointers: void swap(T &x, T &y) { if (&x == &y) return; x ^= y; y ^= x; x ^= y; }
user-the-name 6y ago
You are confused about the problem here. It is not that both values are the same, it is you are applying the xor swap using pointers to values, and both pointers point to the same value in memory.

Straw 6y ago

You can actually extend the XOR trick for missing elements to any fixed number! The standard (non-XOR) low-memory solution calculates the sum of x, x^2, x^3, ..., x^n, which gives enough information to find the missing elements as the roots of an n degree polynomial. We can just do the same thing in the finite field F_{2^k}, where k is the bitwidth of the integers. Addition in this field corresponds to a bitwise XOR, so the first term gives exactly the 1-missing case! I don't remember how to actually solve the resulting polynomial over the finite field though.

dandanua 6y ago
Addition in F_{2^k} is not the same as XORing. But that summation idea is correct. To solve polynomial you can use this algorithm https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algo...
- Straw 6y ago
  Oh, neat, what's the runtime? https://math.stackexchange.com/questions/1479745/relations-of-galois-field-to-bitoperators-in-c https://math.stackexchange.com/questions/1479745/relations-o... What have we missed?
  - dandanua 6y ago
    Ah, XORing is indeed addition in F_{2^k}. It's not addition in Z_{2^k}, though. I was thinking about summation modulo prime number, in this case Z_p = F_p.

j-pb 6y ago

Ah off by one errors are hard: > 1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 1] should be > 1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 2] Because a 0 indexed array of length n-1, has n-2 as it's last index. After all, it's missing a value.

ml_giant 6y ago
Let's try an example with n=4: 1 ^ 2 ^ 3 ^ 4 ^ A[0] ^ A[1] ^ A[2] ^ A[3] It might be early in the morning and I am missing something, but it has n-1 as its last index. Any insight is appreciated :) Edit: There is a missing number in the array, thus its last index is n-2. Thanks for the correction, OP.
- bonzini 6y ago
  But there are only 3 items in the array (for example 1, 2 and 4). So the last valid index is 2.
  - ml_giant 6y ago
    Ah. I was about to make an edit to my comment as you are correct :) Thanks!
- j-pb 6y ago
  Premise: A is containing all values in range [1, 4] except one: Let's say that, without loss of generality: > 1 ^ 2 ^ 3 ^ 4 ^ A[0]=1 ^ A[1]=2 ^ A[2]=3 ^ A[3]=4 However, A is now missing no value. Contradiction. ∎
epsilon-greedy 6y ago
Author here (Florian): I just fixed this. Very good catch. Off-by-one errors are hard indeed. :)

IgorPartola 6y ago

So this is how you’d solve the Fallout 3+ hacking challenges? :) In practice I cannot think of a time when I was confronted with this particular problem. Usually if I need to find a duplicate I have no guarantees that there isn’t more than one or if there is a duplicate at all. I don’t think I’ve ever had to practically solve the “every number but one” problem. Curious where such problems arise in the wild, except interview puzzles.

blauditore 6y ago

This is conceptually almost the same as summing over all entries and comparing to the sum of all numbers in [1, n], except that the latter can be done more efficiently because that sum is simply n*(n+1)/2. There are in fact legit use cases for XOR to speed things up or make algorithms simpler, but this is not the case here IMHO.

abhishekjha 6y ago
XOR handles overflow better than the summing mechanism.

wagslane 6y ago

I recently wrote an article explaining what makes XOR so special - may help put this in context: https://qvault.io/2020/01/18/why-is-exclusive-or-xor-important-in-cryptography/ https://qvault.io/2020/01/18/why-is-exclusive-or-xor-importa...

trinovantes 6y ago

Xor trick may reduce the time/space complexity of a solution but I'd say it definitely increases the cognitive load (maintenance) complexity. Outside of few niche industries/use cases, the increased developer cost will probably outweigh whatever extra hardware you'd need to compensate.

cuspycode 6y ago
Agreed, the XOR trick is just a clever trick that might be useful in some esoteric niche cases, but otherwise don't bother. GCC will even optimize away the XOR operations when this is used for simple things like ints on amd64. I did a simple compile test, and with -O1 and higher I got identical machine code for the XOR algorithm and the naive swapping version. Without optimization I did get the XOR instructions, but the number of machine instructions was longer than for the naive case, and the number of CPU registers used was the same.

exabrial 6y ago

> There are a whole bunch of popular interview questions As a very personal strong opinion, this makes me groan. I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). I'd rather know whether or not they are a pleasant person, are a team player, whether they have leadership aspirations, and take responsibility.

jenwkejnwjkef 6y ago
Nobody wants to see the XOR solutions. These questions are really basic and only filter out the non-programmers. Any decent programmer should be able to solve all of these without a problem.
- dragontamer 6y ago
  I wouldn't say "nobody" wants to see the XOR-trick solution. Its just that those who DO care about it is asking about the general solution: Reed-Solomon codes, or maybe a more modern (harder to understand) variant: like LDPC or Tornado codes. Anyone who needs to recover *ONE* symbol from a data-stream with noise actually needs to recover two, three... four... symbols in the general case. One symbol of erasure recovery is the weakest-of-the-weakest of error correction codes. Its even weaker than the single-error-correction / double-error detection Hamming Code (discovered back in 1950s). XOR-trick is your "basic parity bit", and is the stuff taught to undergrads to wet your appetite for error correction codes (well... erasure correction in this case. Since XOR isn't strong enough to actually correct an error. Only an erasure).
  - shiftingleft 6y ago
    I don't see how the problem corresponds to erasure coding. Typically in erasure coding you know the locations of the erasures. Here, you don't know the location. Maybe you can elaborate on how it relates to erasure coding?

durnygbur 6y ago

I swear this dude interviewed me once.

virgilp 6y ago

Slightly disappointed at the "two missing values" solution: First: one needs to realize that you can solve the "missing number" problem just as well with sums. So, if you're trying to find the "one missing number" between 1 and n, you simply subtract all values from n*(n+1)/2 (the sum of all said numbers) and you end up with the missing one. (using wrap-around semantics, you don't even need to have more bits of memory than you need for the xor solution!) Second: A common way to solve a problem with two variables is to build a system of two equations. One can compute, in a single pass, what is "a+b" and "a^b" ; solve the system, and you get both variables with no additional lookups. Now, it's true that if you get a carry from the addition, this problem might not be solvable...but, if you can afford one extra bit for the potential carry, you're all set.

Strilanc 6y ago
The xor, sum pair can't distinguish missing 11, 0 from missing 10, 1.
- virgilp 6y ago
  Ah, you're right, I didn't think it through. It does feel like there must be a way to play with the bits so that you can retrieve it in a single pass, though - that'd be a much more interesting problem :). (of course, you can do it with sum + product, but that's going to be fairly expensive for large numbers)
slymon99 6y ago
Sums increase in size, however. The nice part of the xor trick is your xor result will be the size of the base of the numbers (64 bits or whatever). If you are reading several tb of 64 bit integers from disk that could get larger than your memory (though unlikely, probably why you see this in kernels where memory might be more of a concern especially with embedded)

all2 6y ago

A = { 1, 2, ... , k, ..., n-1, n}, for 1<=k<=n, and we're given integer n. sum({1..n}) = n(n-1) / 2 sum(A) = n(n-1) / 2 - k k = n(n-1) / 2 - sum(A) Is the interview question looking for a "clever" solution? I'm confused as to why someone would ask this question in an interview? It seems like the more challenging question would be "Find a method of summing a range 1..n in less than O(n) time/space complexity." [edit] I have a dumb. This calculation can happen in O(1). Because of n(n-1)/2, we know the sum of the range, no need to examine each value in the range. [/edit] Or, even more fun, limit the functions/instructions the interviewee can use (ex, some 4 or 5 instructions of x86/WASM/etc. machine instructions, max 1 or 2 registers, etc.) to complete the task.

Vloeck 6y ago
unless n equals 2^17 (or 2^33 if you calculate with longs)

okl 6y ago

For lot's of other fun bithacks, see: https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html

aljarry 6y ago

If you need XOR of two boolean values, you can just "z = x != y". That's my favorite XOR trick, as it's easily understandable and readable.

abhishekjha 6y ago
x!=y is itself calculated using XOR.

simias 6y ago

Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables always being a bit of a bother in C89) in my implementation I decided to implement the swap using the xor trick: s[i] ^= s[j]; s[j] ^= s[i]; s[i] ^= s[j]; I then ran a few basic test vectors, everything seems to work fine. A little while later I noticed that the output of the cypher was weird, the longer it ran the more zeroes I would get, eventually getting only zeroes. The keen reader will already have spotted the problem: whenever i and j happen to be equal instead of doing nothing the code sets the entry to 0 (since x ^ x == 0 for any x). And that's the story of how I never used this trick ever again. In general it's always better to write clear, concise code and let the compiler optimize it. If it turns that the code is performance critical and the compiler doesn't do a good enough job then you can see if the smart solution is worth it. And if you fail an interview because the interviewer expected you to know how to find a duplicate in an integer list by using xor then you probably dodged a bullet anyway. What a silly trivia question.

deleted 6y ago
[deleted]
sleavey 6y ago
I sometimes use your "bug" on purpose in tests, when checking that two values are either both defined or both undefined, but not one defined and one undefined: $ python >>> a, b = 1, 2 >>> bool(a) ^ bool(b) False >>> a, b = 1, 1 >>> bool(a) ^ bool(b) False >>> a, b = None, None >>> bool(a) ^ bool(b) False >>> a, b = None, 1 >>> bool(a) ^ bool(b) True (Note: this doesn't work if a value can be 0, because bool(0) is False in Python). This helps to avoid having to write something like `(a is not None and b is not None) or (a is None and b is None)`.
- shiftingleft 6y ago
  Your note is very important, I think it would be good to give it more emphasis. What works flawlessly, however, is: In [1]: a = None In [2]: b = 0 In [3]: (a is None) ^ (b is None) Out[3]: True Alternatively, as suggested in another comment, you can use inequality as a replacement for XOR: In [4]: (a is None) != (b is None) Out[4]: True Another error prone pattern is the following: In [5]: a or b Out[5]: 0 Which can behave differently depending on the order of elements/values: In [6]: b or a Out[6]: None # should be 0 Since b is zero, it doesn't count. Less error prone, but also more verbose is: In [10]: a if a is not None else b Out[10]: 0

hyperman1 6y ago

A fun party trick not mentioned here is reducing storage in a doubly linked-ish list: Normally each node stores 2 pointers: struct Node {void * prev;void * next} The trick is to use only 1 'pointer', storing prev XOR next: struct Node {void* xored;} While traversing, you remember not only the current position, but also where you came from. So forward traversal goes: next= current.xored XOR previous. Backwards also works: Node * previous=(Node * )current.xored XOR (Node * ) next. The first and last node can use 0 as previous or next node, or you make a circular list. You do have to store a pointer to the first and last node, as usual. I've never seen this used in the real world, which is probably a good thing. It also plays hell with garbage collectors like Boehm, as they can't derive the 2 used adresses. UPDATE: And of course wikipedia knows everything: https://en.wikipedia.org/wiki/XOR_linked_list https://en.wikipedia.org/wiki/XOR_linked_list

user-the-name 6y ago
That is amazing and disgusting.
- abhishekjha 6y ago
  I think there is something like this in linux kernel.
jcmeyrignac 6y ago
I used this trick in a sorting pancakes contest. Flipping a list of pancakes required only one XOR, whatever the size. Very nice trick.
surajrmal 6y ago
The bigger problem with this approach is that you can't remove/erase something from the list just by knowing it's address. This is a key mechanism for most use cases. However, if you're fine with limiting yourself to erasing only during iteration, it's pretty nifty. I've also done some benchmarks in the past and found it interior iteration performance due to what I'm assuming to be inability to prefetch the next address. However, linked list iteration is already relatively slow so I suppose it's not a big downside.

bjkchoy 6y ago

There is a very clever and beautiful algorithm that only uses the xor operation. It's the Luby Transform code, the simplest implementation of a Fountain Code. A Fountain Code lets you transmit a file over an unreliable connection (packets can be unordered, and even lost), with just a unidirectional communication. And this can be done just by xoring a random number of blocks from the file over and over! A very good explanation of the algorithm: http://blog.notdot.net/2012/01/Damn-Cool-Algorithms-Fountain-Codes http://blog.notdot.net/2012/01/Damn-Cool-Algorithms-Fountain...

jng 6y ago

I've known of XOR tricks since the 80s, when you would "undraw" a graphic on the screen by redrawing it with XOR. But only recently I learned that the implementation of multiport memory for CPU caches and the likes often uses a design based on multiple storage copies and XOR to get the last valid written result. Amazed that the CPU's cache is doing that kind of trick all the time just during regular code execution.

utopcell 6y ago

I'd been using xor swapping for years as x ^= y ^= x ^= y; until some point it occurred to me that this has undefined behavior in C.

Aardwolf 6y ago
That's one thing missing from BASIC in other programming languages, the SWAP statement: SWAP x y So few other languages have it, some languages even make it impossible to write a swap function by not supporting pass by reference or pointers. Python has something interesting except it requires typing the name of each variable twice

creeble 6y ago

Fun XOR trick: using it to move a cursor across the screen without having to keep a buffer of the contents under the cursor (and putting them back). It didn't always look great, but if you were moving a full-screen crosshair around, it was sufficient. Especially on hardware that was slow to move buffers to and from ram. Unfortunately, using this pure-math technique was also patented until 2007 [0], much to the surprise of my former employer in 1986. Cadtrak had collected from companies like IBM and NEC and made a nice business as a troll. [0] https://patents.google.com/patent/US4197590B1/en https://patents.google.com/patent/US4197590B1/en

kbelder 6y ago
Really? Apple ][ vector shapes had a XOR mode built in for non-destructively moving shapes across the screen, often used for cursors, and that was released in 1977.

aarchi 6y ago

Even better, store array A instead as a bit set, take the complement, then return the number of trailing zeros plus one.

c2xlZXB5Cg 6y ago

"Nim" game is also solved with XOR. https://en.wikipedia.org/wiki/Nim https://en.wikipedia.org/wiki/Nim

greggman3 6y ago

I've been asked this question before. I don't remember if I already knew the answer or not. But.... When does this ever come up in the real world. > You are given an array of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number. This has happened to me in real life exactly NEVER! I think maybe I was asked you have a list of pairs of integers except one number is missing its pair. Again, no idea where I would apply this in a real world situation.

gnull 6y ago
> This has happened to me in real life exactly NEVER! Do you do something applied like programming? I think problems (and solutions) similar to this one should be easy to find in TCS. The problem you quote seems valuable to me for its insight, it shows that you can reduce certain search problems to algebraic calculations which are easy to do. I think this is useful concept to understand, and a good mental exercise to try coming up with it yourself (even if you don't apply it directly). Could it be that even if you're a programmer who will never have to solve exactly this problem, you could still use the intuition you gain from this problem to solve others (or understand existing solutions you need to implement)? Could it be that you indirectly used the knowledge you have of this solution without being aware of it?
physicles 6y ago
I had a case today where I was comparing two sets for equality. If the range of values is large, you could xor everything together as a O(1) space check for likely equality. Result is nonzero -> sets definitely aren’t equal; result is zero -> sets are probably equal, but you’ll need to check again some other way to make sure. Of course this is absurd if you’re dealing with anything that already fits in ram, but it’s still neat to think about.

strenholme 6y ago

The thing about the “Use XOR to swap two variables” trick is that it’s a version of this solution which works for any two real numbers (or integers): a = a - b b = a + b a = b - a XOR is simply addition or subtraction modulo 2 for each bit, so making the above XOR looks like this: a = a ^ b b = a ^ b a = b ^ a

volta87 6y ago
The article touches on this, since its an important realization. In C, however, if the integers are not unsigned, the add/sub version exhibits UB on overflow, because C unnecessarily ties signed/unsignedness with overflow behavior (UB, two's complement, etc.). Not that this is important, but could hint why this trick is more often shown with XOR than with add/sub.

beeforpork 6y ago

Hmm, I would have used + and -, I suppose. The sum of 1..n is (n*(n+1))/2. Subtract from that all numbers in the array and what is left is the missing number.

NieDzejkob 6y ago
I suppose one downside of this approach is that you need a bigger datatype to contain the result.
- beeforpork 6y ago
  No, not really, because you just need the lower half bits of the multiplication result, i.e., the size you need for your numbers. You do need to care about overflow: the /2 operation must not remove an upper bit from those lower bits. But you can easily do that before *: either n or n+1 is even. Divide the even number by two, then multiply by the odd one and keep only the lower bits. These lower bits are all you need, because the missing number is representable in it: subtracting may use wrap-around, but still, the remaining bits will be the missing number.
marshmellman 6y ago
It’s mentioned in the article that then you need to care about overflow.

crazydoggers 6y ago

My favorite trick is the XOR one time pad. XOR anything (text, images, etc) with a random pad or "key" the same length as the data your are encrypting... and you've got an completely unbreakable cipher. Just be careful as with any one-time-pad cipher. The key needs to be the same length as the data, generated randomly, and you can only use it once... no key reuse ever.

ynfnehf 6y ago

I have never gotten the point of this trick. Don't basically all processors have some equivalent of XCHG (swap contents of two registers)? Even the 8086 had it back in 1978. (The z80 doesn't have it, but it is a couple of years older than 8086.) I tried searching the LLVM source for any mention of the trick, but couldn't find anything. So I can't see it having any relevance to modern CPUs.

truepaurea 6y ago

This can also be seen as roots of matrices and is not exclusive to XOR, it can be done with addition and subtraction. I tried explaining it in [1]. [1]https://paureahack.blogspot.com/2016/04/swap-without-temporary-space.html https://paureahack.blogspot.com/2016/04/swap-without-tempora...

Const-me 6y ago

Good article, but this interview question is not good. > How to swap two numbers without using a temporary variable? I know interviewers expect XOR, but PCs have XCHG instruction. It’s the same error when they asking to compute number of set bits, expecting “lookup table”. Same error when they ask to find the least/most significant set bit index, expecting some bit tricks. Processors have dedicated instructions to do these things, typically faster than smart-ass manual versions. Moreover, for simple things like XCHG, BT, BTC, BSWAP compilers are aware and normally produce them from normally-looking i.e. readable code.

logbiscuitswave 6y ago

I’m a programmer by trade (and I like to think I’m pretty competent), but self-trained. Algorithms have always been a weakness of mine as a result of a lack of formal training. While I use XOR for some simple Boolean comparisons out of convenience, the kind of XOR use I see —- especially in crypto libraries has always been very mysterious to me. This article cleared up a lot of that for me. That being said, I often prefer readability over fancy so I don’t imagine using these tricks regularly but it’s nice to better understand how they work. This article did a great job demistifying this practice.

blt 6y ago

On a less clever note, I also find it useful to think about XOR as the "conditional inversion" operator: x invert? out 0 0 0 1 0 1 0 1 1 1 1 0 This has saved me some nested if-statements before.

seanwilson 6y ago

I've used XOR for undo/redo when I had limited memory in a painting app: - You have the canvas in state S before you draw on it and the canvas in state T after you draw on it. - Store (S XOR T). XOR this against T to undo back to S and XOR again to redo back to T. So if you want to have 10 levels of undo, you only need to store the final state and the 10 XOR diffs that got you there. The diffs will compress well too because most of the pixels on them will be blank (where nothing changed). All fairly easy to implement too e.g. compared to storing and replaying high-level commands to redo.

Fazel94 6y ago

> Arithmetic operators instead of XOR In that case, It uses Python that supports arbitrary long numbers out of the box so overflow of integers wouldn't be an issue(in Python3 default is arbitrary long integers).

sarcarx 6y ago

Note that the combined xor of the first n integers can be computed in constant time (oeis.org/A003815). a(4n)=4n, (4n+1)=1, a(4n+2)=4n+3, a(4n+3)=0