h1

Puzzle #3

June 4, 2007

OK, you seem to like them so here is another puzzle/interview question.

In the diagram below both X and Y are n-bit wide registers. With each clock cycle you could select a bit-wise basic operation between X and Y and load it to either X or Y, while the other register keeps its value.
The problem is to exchange the contents of X and Y. Describe the values of the “select logic op” and “load XnotY” signals for each clock cycle.

load_puzzle.png

Advertisements

6 comments

  1. This one works on confusion. XOR (^) is all you need here. Remember that
    X^X=0 and that X^0=X
    So:
    X,Y (XOR, store in X)
    X^Y,Y (XOR, store in Y)
    X^Y,Y^(X^Y) = Y^Y^X = 0^X = X (XOR, store in X)
    X^(X^Y) = Y,X
    (done)


  2. Good job Saar!!!


  3. […] – Solution June 19th, 2007 This post is written only for completeness reasons. The answer to puzzle #3 was almost immediately given in the comments. I will just repeat it here. The important […]


  4. x = x^y — [1]
    y = x^y
    from [1], y =(x^y)^y = x –[2]
    x = x^y
    from[1] & [2] x= =(x^y)^x = y


  5. solution is

    x = x ^ y;
    y = x ^ y;
    x = x ^ y;

    for alu select xor operation, and xnoty 1, 0 , 1 for seleting x y and x as destination register.


    • 1) loadxnoty=1 , selectlogicop = xor
      (x) -> x^y , (y) -> y
      2) loadxnoty=0 , selectLogicOp = xor
      (x) -> x^y , (y) -> (x^y)^y = x
      3) loadxnoty=1 , selectLogicOp = xor
      (x) -> (x^y)^x = y , (y) => x

      o/p = (x^y)^y
      x | y | o/p |
      0 | 0 | 0 |
      0 | 1 | 0 |
      1 | 0 | 1 |
      1 | 1 | 1 |

      Therefore (x^y)^y = x



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: