Докажите, что каждое неотрицательное целое единственным образом представляется суммой различных степеней двойки.
Quant ResearchУровень: ПрактикаBinary representation
Докажите, что каждое неотрицательное целое единственным образом представляется суммой различных степеней двойки.
Подсказки
- Стройте представление делением с остатком.
- Сравните младший различающийся бит.
Ответ
Существование: делите на 2, записывая остатки 0 или 1. Для единственности возьмите младший различающийся бит: его вклад — нечётное кратное 2^k, все старшие дают чётные кратные, сумма не ноль. Ноль — пустая сумма.
Источник и лицензия: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · ответ: редакция Quantoros · перевод: Quantoros