Proof that $(X \mod 2^n) = X \textrm{ AND } (2^n - 1)$ for $n \geq 0$

Question

When doing binary arithmetic, calculating the remainder of a division by a power of 2 can be done using a bitwise $\textrm{AND}$. For $n \geq 0$ we have that:

$(X \mod 2^n) = X \textrm{ AND } (2^n - 1)$

I can see from some examples why it works, but I would like to know a general proof for this. I lay out two cases which can be generalized, but I would like to know if this reasoning constitutes a proof.

Dividing by 2

The simplest, non-trivial case is dividing by 2.

$ 2_{10} = 10_{2} $

If $X$ is an n-bit even number, it will have the form

$ x_0 x_1...x_{n-1}0$

If it is odd, then it will end on a 1

$ x_0 x_1...x_{n-1}1$

Applying the bitwise $\textrm{AND}$ we get that for an even number

$ x_0 x_1...x_{n-1}0 \textrm{ AND } 0...01 = 0$

For an odd number

$ x_0 x_1...x_{n-1}1 \textrm{ AND } 0...01 = 1$

Dividing by 4

When dividing by 4, the remainder can be either 0, 1, 2 or 3.

Case 1: $ X \equiv 0 \pmod{4}$

In this case, $X$ will have the form

$ x_0 x_1...x_{n-2}00$

And applying bitwise $\textrm{AND}$ with $2^n -1$ we get

$ x_0 x_1...x_{n-2}00 \textrm{ AND } 0...011 = 0$

Case 2: $X \equiv 1 \pmod{4}$

$X$ has the form

$ x_0 x_1...x_{n-2}01$

So that

$ x_0 x_1...x_{n-2}01 \textrm{ AND } 0...011 = 1$

Case 3: $X \equiv 2 \pmod{4}$

$X$ has the form

$ x_0 x_1...x_{n-2}10$

So that

$ x_0 x_1...x_{n-2}10 \textrm{ AND } 0...011 = 10$

Case 4: $X \equiv 3 \pmod{4}$

Finally, in this case $X$ will have the form

$ x_0 x_1...x_{n-2}11$

So that

$ x_0 x_1...x_{n-2}11 \textrm{ AND } 0...011 = 11$

Generalizing these results

I can see how this proof can be generalized for all powers of 2: in the case of 4, any number divisible by 4 ends with two zeroes when in binary representation. For any number divisible by 8, it has to end with three zeroes, and so on.

Is there a simpler, and perhaps more rigorous way to prove that $(X \mod 2^n) = X \textrm{ AND } (2^n - 1)$?

Answer 1

AND only cares about common 1's, $2^n-1$ is the sum of all lower powers of 2 (aka base 2 repunit). The AND then, only cares about those 1's below the $2^n$ place. That makes the result less than $2^n$ and only contain the 1's set in X. By clearing all bits above $2^n$ you've subtracted a multiple of $2^n$ . That makes the bits that are 1, read out the remainder on division by $2^n$ . It really is that simple.