What is the function of bitwise & in this statement?

Question

I have been reading about an implementation of the diamond-square algorithm in C# that wraps around to create seamless textures. To calculate the next point, an average is taken of four sample points arranged in a square or a diamond. If a sample point lies of the edge of the texture, it is wrapped around to the other side. This wrapping appears to be done using the following method:

public double sample(int x, int y)
{
    return values[(x & (width - 1)) + (y & (height - 1)) * width];
}

A little bit of research tells me this is a bitwise operator. I have not used them before, and the wikipedia article was not enlightening. Could someone explain what the & operator is doing in this method?

EDIT: The texture dimensions are always powers of two

Answer 1

It's for the "wrapping". Assuming width and height are powers of two (otherwise it doesn't work, so that had better be true), x & (width - 1) is mostly equivalent to x % width, except that it also works for negative x (whereas x % width with a negative x would have a negative result) and is almost certainly faster.

Or to put it visually with an example, say width = 64 and x = 64+12 = 76, then

x       = 00000000 00000000 00000000 01001100
w       = 00000000 00000000 00000000 01000000
w-1     = 00000000 00000000 00000000 00111111
x & w-1 = 00000000 00000000 00000000 00001100 = 12

As you can see from the form of w-1, the operation x & w-1 is like taking only the bottom bits of x, assuming of course that w is still a power of two. So the bits with weights 64 and multiples of 64 are removed, just as a true "modulo 64" operation would (which is not % in C# if you are working with signed integers, that's a remainder).