Как доказать, что m% n эквивалентно m & (n-1), когда n равно 2 ^ k?

Question

Обратите внимание, что '%' - это оператор остатка, '&' - это побитовый оператор AND, а k - целое число больше 0.

Пример:

33%16=1 equivalent to 33&(16-1)=1

Я обнаружил этот эквивалент в JDK1.8 ThreadLocalMap. Я знаю, что это правильно, но не знаю, как доказать, что это правильно. Буду признателен, если вы окажете помощь.

Answer 1

m % n - это остаток от деления m на n и, следовательно, число от 0 до n-1 или от 0 до 2 ^ k - 1.

2 ^ k в двоичном формате - это единица, за которой следует на k нулей. 2 ^ k -1 - это k смежных единиц.

m & n - это m & (2 ^ k - 1) - это число, в котором в двоичном формате бит 1 должен находиться в крайних правых k битах. Следовательно, он находится в диапазоне от 0 до 2 ^ k - 1.

QED.