Смесь двоичной и десятичной арифметики

Многие знают, что происходит при выполнении присваивания "n &= (n - 1);" просто потому, что это весьма распространенный шаблон, и для чего может понадобиться выполнение его в цикле, пока n не станет нулем.

Интересно другое: четкое математическое (и/или алгоритмическое) объяснение, почему это работает именно так, строгое доказательство.


Update:

Чтобы разобраться в вопросе надо понять, что является корнем недопонимания.

Для людей, не часто имеющих дело с двоичной системой, обычно не совсем очевидна суть трансформации внутреннего двоичного представления числа при выполнении арифметической операции в десятичной нотации. Кажется, что если вычесть единицу, то расположение битов после операции будет иметь мало общего с тем, что было до вычитания. И дальнейшее выполнение "and" вообще не имеет смысла.

С точки зрения битового представления любого числа, есть только два случая:

1. Если число нечетное, на конце будет единица: "xx...xx1". Вычитание из такого числа даст: "хх...хх0". Поэтому "(xx...xx1) & (xx...xx0)" даст "(xx...xx0)". Фактически, мы убрали младший бит.

2. Если число четное, на конце будет ноль (или несколько нулей): "xx...xx100...00". Видно, что вычитание единицы из такого числа однозначно не изменит разряды "xx...xx", стоящие слева после первой единицы. Более того, результат вычитания единицы однозначно предсказуем: "xx...xx011...11". Теперь точно видно, что будет после операции "and": ("xx...xx100...00") & ("xx...xx011...11") даст ""xx...xx000...00". То есть мы убрали единицу из самого младшего ненулевого разряда.

Теперь ясно видно, что именно проиходит в присваивании "n &= (n - 1);". А именно, обнуление самого младшего ненулевого разряда.

Использование этого трюка в цикле, пока n не равно нулю, позволяет подсчитать количество ненулевых бит. На каждой итерации мы "выбиваем" ровно один бит, поэтому Число итераций будет равно количеству единиц в n.