Dividing an integer number $k$ by $2^n$ (i.e., computing $\lfloor k/(2^n)\rfloor$) is easy: it is just equivalent to bitshifting $k$ by $n$ binary places, therefore removing the last $n$ binary digits and then shifting the remaining digits down by $n$ digits.
Same thing goes for modulo operations: if I want to compute $(k)_{mod\, 2^n}$ I just need to take the $n$ least significant digits of $k$ and I am done.
I was wondering if there is a reasonably simple way to do the same thing, but with $2^n-1$. Be $k$ an integer number, represented in binary format, is it possible to compute $\lfloor k / (2^n-1)\rfloor$ and $(k)_{mod\,2^n-1}$ without having to go through the whole division process?
Calculating $(k)_{\bmod(2^n-1)}$ is easy: Just split the number in blocks of length $n$ bits, remove all those block that consist of all $1$ bits, and add up the rest. Repeat until only one block is left. If that block consists of only $1$ bits, replace it by $0$.
Example:
$(163)_{\bmod (2^2-1)} = (10100011_2)_{\bmod 3}$.
Split into pairs of bits: $10,10,00,11$.
Remove the pairs of all $1$ bits, and add up the rest: $10_2 + 10_2 + 00_2 = 100_2$
That's more than 2 digits, so repeat: $100_2 \rightarrow 01,00 \rightarrow 1_2$
Now you arrived at a number of not more than 2 digits. Since it doesn't consist of all $1$ (as 2-digit number it's $01$), you don't replace it by $0$.
Thus $(163)_{\bmod (2^2-1)} = 1$. You can easily verify that this is true.
So why does this work? It's actually quite simple: $b = (b-1) + 1$, and therefore $b\equiv 1 \pmod {b-1}$. Therefore if you write a number in base $b$ (and an $n$-digit block is actually a digit in base $2^n$), then you get $k = \sum a_k b^k \equiv \sum a_k 1^k = \sum a_k\pmod {b-1}$. The omitting of all-$1$ blocks makes use of the fact that the all-$1$ block is $2^n-1$, and obviously $b-1\equiv 0\pmod {b-1}$.