Can someone explain this bitwise array-wrap-around expression?
Question: I've been researching on the Diamond-square algorithm and I came across [this
website](http://www.bluh.org/code-the-diamond-square-algorithm/) which pointed
me to the source code of Notch's Minicraft, and does a conversion of the
algorithm as was implemented by Notch.

For the most part I understand the algorithm, but I can get my head around the
specific expression found in these two functions:

    
    
    private double sample(int x, int y) {
        return values[ (x & (w - 1)) + (y & (h - 1)) * w ];
    }
    
    private void setSample(int x, int y, double value) {
        values[ (x & (w - 1)) + (y & (h - 1)) * w ] = value;
    }
    

I do understand `x + y * w`, but not `(x & (w - 1)) + (y & (h - 1)) * w`, and
the article doesn't explain this besides stating that it serves to wrap-
around.

I'm coding in python, but I don't think there's any difference between Java's
bitwise `&` and python's, so I fiddled with it a bit but I still can't get it.
One of the things I did was a loop that simulates varying `x` and `y` values
and feeds them to that calculation:

    
    
    import random
    w = h = 257     # 2^8 + 1
    for i in xrange(10):
        x = int(random.uniform(0, 1) *255)
        y = int(random.uniform(0, 1) *255)
    
        print x, y, '|', (x & (w-1)) + (y & (h-1)) *w
    
        # I used a less readable right-aligning version of the above to display the output:
        # print str( x ).rjust(3), str( y ).rjust(3), '|', str( (x & (w-1)) + (y & (h-1)) * w ).rjust(3)
    

Output:

    
    
    112 213 |   0
    181 117 |   0
      1 105 |   0
    216 223 |   0
    170 185 |   0
    158  32 |   0
    124 225 |   0
     62 153 |   0
     90 147 |   0
    196  69 |   0
    

Unless I'm doing something fundamentally wrong here, it always gives me zero,
unless `x` and/or `y` are equal to `w-1`, in which case:

    
    
    256  15 |   256
     21 256 | 65792
    256 256 | 66048
    

In the actual algorithm the value of `x` and `y` seems to always be (if I
understand correctly) somewhere between `0` and `halfStep`, where `halfStep =
stepSize/2`, `stepSize = featureSise` which seems to be (in Minicraft's code)
always hardcoded as `16` or `32`. So according to my current understanding
that expression would always evaluate to `0`.

So I'm confused. I don't see how this is useful or how it actually works in
practice... I know it works, but it seems like sorcery... I understand how the
bitwise `&` works, but that doesn't seem to help.


Answer: `w` and `h` must be powers of 2 (and represent the local bounds for `x` and
`y`, respectively). Then, `w-1` and `h-1` are sequences of ones. One for each
bit of information which could possibly contribute to a value lower than `w`
and `h` (and still be `>= 0`), respectively.

When you now evaluate the bit-wise _and_ (`&`), e.g. `x & (w-1)`, this will
actually yield `x % w`, where `%` is the modulo operation in python, for `x >=
0`. Thus, `x` is mapped to `x` if `w > x >= 0` and otherwise `x` is truncated
(zeroing higher bits), such that `w > x >= 0` is satisfied. The same applies
to `y` and `h`.

Consequently, these logical operations are nothing more than evaluating _mod_
on a bit-level.

For your code: Set `w=h=256` and everything should work out.

