К содержанию
Quantoros

Докажите, что каждое неотрицательное целое единственным образом представляется суммой различных степеней двойки.

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

Похожие вопросы