The squares of an infinite chessboard are numbered successively as follows: in the lower left corner (first row, first column) we put 0 (zero), and then in every other square we put the smallest nonnegative integer that does not appear to its left in the same row or below it in the same column. See it partially filled:

            |   |   |   |   |   |   |   |   |
            +---+---+---+---+---+---+---+---+--
            | 5 |   |   |   |   |   |   |   |
            +---+---+---+---+---+---+---+---+--
            | 4 | 5 |   |   |   |   |   |   |
            +---+---+---+---+---+---+---+---+--
            | 3 | 2 | 1 |   |   |   |   |   |
            +---+---+---+---+---+---+---+---+--
            | 2 | 3 | 0 | 1 |   |   |   |   | 
            +---+---+---+---+---+---+---+---+--
            | 1 | 0 | 3 | 2 | 5 |   |   |   |
            +---+---+---+---+---+---+---+---+--
            | 0 | 1 | 2 | 3 | 4 | 5 |   |   | 
            +---+---+---+---+---+---+---+---+--

Find the law that rules the numbers that fills the chessboard, so that in seconds, you can evaluate the number that is, for example, in the intersection of the 1000th row and the 100th column.

Those who programmed in COBOL, FORTRAN, and specially in ASSEMBLER (assembly language), a thousand years ago:

In Assembler, the XOR (Exclusive OR) was denoted by XR (not a symbol, the operation), and we used it a lot, when we had to exchange two variables, without a "temporary area in memory", that is: A-->T, B-->A, T-->A. We have to use the less memory possible in the computers.

XR(a,b) was defined as the binary sum of a and b, WITHOUT CARRYING, and the result was put in a. 

Look at what XOR (XR) does:

A = 3 (in decimal) -------> A = 11 (in binary)
B = 4 (in decimal)--------> B = 100 (in binary)

XR(A,B) = 111, so A becomes 111 and B remains 100.
XR(B,A) = 100, so B becomes 011 and A remains 111.
XR(A,B) = 100, so A becomes 100 and B remains 011.

Now, A = 100 (4 in decimal) and B = 011 (3 in decimal).

We interchanged the values A and B without a "temporary area in memory". 

Edited on October 29, 2005, 7:39 am

Edited on October 29, 2005, 7:56 am

Posted by pcbouhid on 2005-10-28 20:27:18