Need to know if a number is divisible after an operation

Question

I have a number on which I perform a specific operation I want to make sure that the number is still divisible after the operation.

Let's say I have an integer x which is divisible by PAGE_S

does this produces an integer which is also divisible by PAGE_S ?

x^ ~(PAGE_S-1);

so (x % PAGE_S) == ( (x^ ~(PAGE_S-1)) % PAGE_S) ? As far as I tested, it works, but I need to understand why...

p.s this is part of a code of translating virtual memory addresses to physical addresses

Answer 1

Yes, but only if PAGE_S is a power of two.

If PAGE_S is a power of two (say, 2^k), then its binary representation is a 1 followed by k 0s. So, PAGE_S-1 will be k 1s in binary, so ~(PAGE_S-1) is all 1s followed by k 0s.

The xor operation (^) will flip any bits of the first operand for which the corresponding bit in the second operand is 1; for example, 101101 ^ 111000 is 010101 because the first three bits are flipped.

Since x is divisible by PAGE_S, the last k bits must be zero. Since the last k bits of ~(PAGE_S-1) are also zero, the last k bits of x^~(PAGE_S-1) are zero so it is divisible by PAGE_S. This also inverts all the other bits of x.