Необычное бинарное представление нечетного числа

[MGM]

Стандартное бинарное представление любого целого числа:
$c = \sum\limits_{i = 0}^\infty {{b_i}{2^i}} $,
где ${b_i} \in \left\{ {0,1} \right\}$.
Найти алгоритм для нетипичного бинарного разложения:
${\bar c} = \sum\limits_{i = 0}^\infty {{\bar b_i}{2^i}} $,
где ${\bar b_i} \in \left\{ { - 1,1} \right\}$, а ${\bar c} $ - любое нечетное число.

PS Если есть предположение, для чего такое разложение было бы нужно - поделитесь соображениями.
Возможно, что задачка простая, и даже входит в какой-нибудь курс, в качестве ДЗ, тем не менее я регулярно забываю ее решение.

[RIP]

Да просто сделать замену $\bar{b}_{i}=2b_{i}-1$ и раскладывать

$$\frac{\bar{c}-1+2^{n}}{2}=\sum_{i=0}^{n-1}b_{i}2^{i},$$

где $2^{n}>\lvert\bar{c}\rvert$. Бесконечной сумма, конечно, быть не может.

[MGM]

Здорово. Первая часть годится с первого взгляда и для четных. Попробовал по вашей формуле разложить число 5... Не пойму, где подвох...:)
Бесконечность, конечно не совсем удобное, но означает лишь, что число нулей может быть неограничено. Ваше ограничение на степень двойки дает единственное решение, хоть и довольно странное.
То есть вторая половина похоже верная, но не понятно как ей пользоваться.

[MGM]

Даю уточнение:
$c = \bar c$
Как получить разложение
$c = \sum\limits_{i = 0}^I {{b_i}{2^i}} $
знают даже школьники.
А вот как получить разложение
$\bar c = \sum\limits_{i = 0}^I {{{\bar b}_i}{2^i}} $
из формулы предыдущего поста мне не ясно.

[RIP]

Во втором случае не может быть бесконечности, потому что нули запрещены.

Если $\bar{c}=5<2^3$, то

$$\frac{\bar{c}+2^3-1}{2}=6=0\cdot2^0+1\cdot2^1+1\cdot2^2 \implies 5=(-1)\cdot2^0+1\cdot2^1+1\cdot2^2.$$

Можно и по-другому: $\bar{c}=5<2^5$, поэтому

$$\frac{\bar{c}+2^5-1}{2}=18=0\cdot2^0+1\cdot2^1+0\cdot2^2+0\cdot2^3+1\cdot2^4 \implies 5=(-1)\cdot2^0+1\cdot2^1+(-1)\cdot2^2+(-1)\cdot2^3+1\cdot2^4.$$

(То есть разложение не единственно.)

[MGM]

OK. Принято. Хотя мне лично трудно понять алгоритм.
Поэтому публикую свой.
Определим четыре числа и их классические бинарные разложения.
1. Собственно само число, которое необходимо разложить:
$\alpha = \sum\limits_{i = 0}^I {{a_i}{2^i}} $
$\bar \alpha = \sum\limits_{i = 0}^I {{{\bar a}_i}{2^i}} $
2. Неизвестное число положительный компонент:
$\rho = \sum\limits_{i = 0}^I {{p_i}{2^i}} $
3. Неизвестное число отрицательный компонент:
$\mu = \sum\limits_{i = 0}^I {{m_i}{2^i}} $
4. Вспомогательное число:
$\beta = {2^{I + 1}} - 1$
Определим соотношение первых трех чисел, как:
$\alpha = \bar \alpha = \rho - \mu $
Тогда:
$\beta + \bar \alpha = 2\rho $
и мы получаем два неизвестных:
$\left\{ \begin{array}{l} \rho = \frac{{\beta + \alpha }}{2}\\ \mu = \frac{{\beta - \alpha }}{2} \end{array} \right.$
Окончательно формула разложения:
$\alpha = \sum\limits_{i = 0}^I {{p_i}{2^i}} - \sum\limits_{i = 0}^I {{m_i}{2^i}} = \sum\limits_{i = 0}^I {\left( {{p_i} - {m_i}} \right){2^i}} = \sum\limits_{i = 0}^I {{{\bar a}_i}{2^i}} = \bar \alpha $
Легко доказывается, что$ {p_i} \ne {m_i}$, а следовательно,
${{\bar a}_i} = \left( {{p_i} - {m_i}} \right) \in \left\{ { - 1,1} \right\}$

[RIP]

MGM в сообщении #1593653 писал(а):

Хотя мне лично трудно понять алгоритм.

Делаем замену $\bar{b}_{i}=2b_{i}-1$, так что $\bar{b}_{i}\in\{\pm1\} \iff b_{i}\in\{0,1\}$. Тогда (мне удобнее переобозначить $n=I+1$)

$$\bar{c}=\sum_{i=0}^{n-1}\bar{b}_{i}2^{i} \iff \frac{\bar{c}+2^{n}-1}{2}=\sum_{i=0}^{n-1}b_{i}2^{i}.$$

Последнее равенство возможно тогда и только тогда, когда

$$0\leqslant\frac{\bar{c}+2^{n}-1}{2}\leqslant2^{n}-1 \iff \lvert\bar{c}\rvert\leqslant2^{n}-1.$$

Соответственно, алгоритм:
1. Берём натуральное $n$, такое что $2^{n}>\lvert\bar{c}\rvert$.
2. Представляем число $\frac{\bar{c}+2^{n}-1}{2}$ в двоичной системе:

$$\frac{\bar{c}+2^{n}-1}{2}=\sum_{i=0}^{n-1}b_{i}2^{i}.$$

3. Заменяя в этом представлении каждое $b_{i}=0$ на $-1$, получаем искомое представление для $\bar{c}$.

Или я неправильно понял задачу?

[MGM]

В принципе я понял почти сразу ваш алгоритм.
Есть подозрение, что он идеально подходит для нетипичного разложения в троичной системе счисления. Точнее, полная уверенность.
И для случая со степенями тройки все гороздо проще и действительно в два шага.
Для двойки самый неудобный момент - ассиметрия относительно базы состоящей из
$ \beta = {2^{I + 1}} - 1$.

PS Для тройки (есть смутное подозрение, что это давно известно и без меня):
$\bar Y = \sum\limits_{i = 0}^I {{{\bar y}_i}{3^i}} = X - \sum\limits_{i = 0}^I {{3^i}} \Rightarrow $
$X = Y + \sum\limits_{i = 0}^I {{3^i}} = \sum\limits_{i = 0}^I {{x_i}{3^i}} \Rightarrow $

$\bar Y = \sum\limits_{i = 0}^I {\left( {{x_i} - 1} \right){3^i}} $
${{\bar y}_i} \in \left\{ { - 1,0,1} \right\}$

[TOTAL]

Просто заменяем все куски стандартного двоичного представления (старшие разряды слева)
$0,0,0,0,0,1 \rightarrow 1,(-1),(-1),(-1),(-1)$

[RIP]

Для тройки можно и без замены, поскольку $\{-1,0,1\}$ — полная система вычетов по модулю $3$. Для целых чисел алгоритм, основанный на делении с остатком, работает без изменений.