Print a specific value in the infinite Walsh matrix

GolfScript (18 15 14 bytes)

~&2base-1\0-,?

Takes input space-separated; outputs to stdout. Thanks to Howard for pointing out that the space in the 15-char solution was removable.

The way I reasoned to this solution is quite simple. Take the highest set bit of x|y: this tells you the size of the smallest Walsh matrix which contains the relevant index. Then clearing that bit in both x and y drops us down to the top-left quadrant, and we need to multiply by -1 if we were previously in the bottom-right quadrant: i.e. if the bit was set in both x and y. By induction down the bit sequence, we just need to count the number of bits set in x&y.

Forth (gforth), 44 bytes

: f and 1e 63 for s>d 2* 1+ s>f f* 2* next ;

Try it online!

The function takes two word-sized unsigned integers (64 bits on TIO). It returns -1 or 1 on the floating-point stack and leaves a garbage 0 on the main stack.

The algorithm follows Blckknght's submission, but the task made me explore LOTS of possibilities for writing Forth programs - from bit shift, divmod, single-to-double conversion to abusing floating-point stack. (The TIO link has several alternative definitions of f which all work, but are longer than the main answer.)

How it works

: f ( u1 u2 -- -1e_or_1e )  \ Takes two integers and returns a float 1 or -1
  and 1e                    \ Bitwise and(=N), then put a 1(=R) on the FP stack
  63 for                    \ Repeat 64 times... (TIO gforth has 64-bit cells)
    s>d                       \ Sign-extend single N to double
                              \ In effect, 0 is pushed if MSB is zero, -1 otherwise
    2* 1+ s>f f*              \ Change 0_or_-1 to 1_or_-1, cast to float and multiply with R
    2*                        \ Shift N left once
  next                      \ End loop
  ;                         \ End function

Python 2 - 42 bytes

print(-1)**bin(input()&input()).count("1")

This takes the two coordinates as separate lines on standard input and writes the answer to standard output.

The algorithm is this:

1. For coordinates X and Y, find X & Y, the bitwise AND of their values.
2. Count the number of 1 bits in X & Y. This is the number of times the requested coordinate is in the bottom right quadrant of a level of the matrix.
3. If the count is odd, the result is -1. If the count is even, the result is 1.

This should work for any positive integer coordinates (including large ones that need more than 32 bits).