Getting modulus from `&`

Question

Possible Duplicate:
Why is modulo operator necessary?

I need help understanding how does & give the modulus? I am working on an assignment to use memory access times to determine the cache sizes. Currently I am getting wierd results for the L3 size. I think it has something to do with & only working well for powers of 2, or something like that? So I want to understand how it actually works

lengthMod = 1024/sizeof(int) - 1;
for (unsigned int k = 0; k < REPS; k++) {
    data[(k * 16) & lengthMod]++;
}

Will & always work? Or does it only work with some values? What actually happens for other values?

http://stackoverflow.com/questions/10097534/why-is-modulo-operator-necessary — Mysticial, Oct 05 '12 at 02:02

score 2 · Answer 1 · answered Oct 05 '12 at 02:02

2

& is the binary "and" operator. The operator for modulus is %.

answered Oct 05 '12 at 02:02

Lily Chung

2,919
1
25
42

`&` works fine as a modulus if it's done with (2^n -1). – paxdiablo Oct 05 '12 at 02:16

score 1 · Answer 2 · edited Oct 05 '12 at 02:15

1

& does a bit-wise and operation between the two values. For modulus, you'd want to use the % operator:

int x = 23 % 7; // x = 2

edited Oct 05 '12 at 02:15

Brendan Long

53,280
21
146
188

answered Oct 05 '12 at 02:03

Darius Makaitis

880
1
5
5

score 1 · Accepted Answer · answered Oct 05 '12 at 02:08

To expand on the other answers, if you take the modulus of a positive number and a positive power of 2 (i.e. a % b where b is a power of 2 and a and b are positive), you can effectively replace the % operator with the & operator (and subtract 1 from b, so it becomes a & (b - 1)).

This is because the & operator does a bit-wise mask, and the result of a number mod a power of two is just going to be the lower bits of that number.

This only works when the right hand argument is a power of two and both numbers are positive. Otherwise, use the % operator.

Getting modulus from `&`

3 Answers3