Двоичное представление со знаком

[Alik]

Здравствуйте, у меня вопрос касательно суммы цифр в так называемом signed-digit binary representation. Рассмотрим в качестве примера:
$5=4+2-1\rightarrow\lbrace0\;1\;1 -1\rbrace$, с другой стороны
$5=8-4+1\rightarrow\lbrace1-1\;0\;1\rbrace$. Сумма цифр в обоих кодах равна $1$.
Эксперимент проведенный для чисел меньше 16 показывает, что для каждого из них можно найти код обладающий указанным свойством:
$1\rightarrow sum(0 0 0 1)=1$
$2\rightarrow sum(0 0 1 0)=1$
$3\rightarrow sum(0 1 -1 1)=1$
$4\rightarrow sum(0 1 0 0)=1$
$5\rightarrow sum(0 1 1 -1)=1$
$5\rightarrow sum(1 -1 0 1)=1$
$6\rightarrow sum(1 -1 1 0)=1$
$7\rightarrow sum(1 0 -1 1)=1$
$8\rightarrow sum(1 0 0 0)=1$
Вопрос как эти коды получать (метод перебора не подходит), т.е. нужен алгоритм, на входе которого обычный бинарный код, а на выходе один или несколько кодов со знаком.

[bot]

Одного хватит?
Стартуем с обычного бинарного предствления. Используя тождество
$2^n+2^{n-1}+\dots +1=2^{n+1}-1$ заменяем начиная со старших разрядов группу единиц между двумя нулями на $\pm 1$ с нулями между ними. Последнюю единичку, даже если она была в группе единиц, оставляем.

-- Пн окт 10, 2011 23:29:17 --

Собссно оставить можно не оязательно самую младшую единичку, а младшую в любой группе единиц.
Не слишком ли смело на засыпающую голову будет высказать предположение, что так все получатся?

-- Пн окт 10, 2011 23:37:16 --

Это просто нахальство было бы $1\rightarrow 1-1-1-1$

[Alik]

bot, спасибо большое. Обещаю проверить и позадавать вопросы.

[Alik]

Эта задачка по духу очень напоминает
http://en.wikipedia.org/wiki/Non-adjacent_form
за исключением двух мелочей
1) the representation is not unique
2) its Hamming weight is varying

[Alik]

Пока что таблица для $N\leq 16$:

$ \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 5 \\ 6 \\ 7 \\ 7 \\ 8 \\ 9 \\ 9 \\ 10 \\ 10 \\ 11 \\ 11 \\ 12 \\ 13 \\ 13 \\ 14 \\ 15 \\ 16 \\ \end{bmatrix} \overset{sbin }{\rightarrow} \begin{bmatrix} 0 0 0 0 1 \\ 0 0 0 1 0 \\ 0 0 1 \bar{1} 1 \\ 0 0 1 0 0\\ 0 0 1 1 \bar{1}\\ 0 1 \bar{1} 0 1\\ 0 1 \bar{1} 1 0 \\ 0 1 0 \bar{1} 1\\ 1 \bar{1} \bar{1} 1 1\\ 0 1 0 0 0\\ 0 1 0 1 \bar{1} \\ 1 \bar{1} 0 0 1\\ 0 1 1 \bar{1} 0\\ 1 \bar{1} 0 1 0 \\ 0 1 1 0 \bar{1}\\ 1 \bar{1} 1 \bar{1} 1\\ 1 \bar{1} 1 0 0 \\ 1 \bar{1} 1 1 \bar{1}\\ 1 0 \bar{1} 0 1 \\ 1 0 \bar{1} 1 0\\ 1 0 0 \bar{1} 1 \\ 1 0 0 0 0\\ \end{bmatrix} \overset{sum }{\rightarrow} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ \end{bmatrix} $