Print a specific value in the infinite Walsh matrix

Question

The Walsh matrix is an interesting fractal matrix with the property that every single value in a Walsh matrix has a value of either -1 or 1. Additionally, the size of a Walsh matrix is always a power of 2.

Because each Walsh matrix is identical to the top-left quarter of the immediately higher-order Walsh matrix, we can create a generalized "infinite Walsh matrix" by considering the limit of the sequence of Walsh matrices of order N, as N goes to infinity. From here on, we will call this infinite generalization the Walsh matrix.

Your task is to build a program that takes the coordinates of a location in the Walsh matrix and returns the value that occurs there.

Your program will accept two integers x and y as input (in any form you choose), and output the value that appears in the x+1th row of the y+1th column of the Walsh matrix. For example, the input

2 5

will return 1, as the 3rd row in the 6th column of the Walsh matrix has a value of 1. The input

6 4

will return -1, as the 7th row in the 5th column of the Walsh matrix has a value of -1. The input

2834719 394802

will return -1, as the 2384720th row of the 394803rd column has a value of -1.

The shortest code to do this in any language wins.

Answer 1

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.

Answer 2

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

Answer 3

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).

Answer 4

x86_64 machine language for Linux, 17 bytes

0x00:  48 21 F7          and    rdi, rsi
0x03:  F3 48 0F B8 C7    popcnt rax, rdi
0x08:  FF C0             inc    eax
0x0a:  24 01             and    al, 1
0x0c:  01 C0             add    eax, eax
0x0e:  FF C8             dec    eax
0x10:  C3                ret    

Same algorithm as @Blckknght's answer.

Try it online!

Answer 5

K (ngn/k), 18 16 bytes

-2 bytes by converting to tacit form

-:/[;1]@+/&/+2\,

Try it online!

Based off of @Blckknght's Python 2 answer.

• &/+2\, take the (equivalent of) the bitwise-and of x and y
• +/ do a popcnt (i.e. number of bits set to 1)
• -:/[;1]@ negate 1 that many times and return