В математика, кодирование негаФибоначчи это универсальный код который кодирует ненулевые целые числа в двоичную систему кодовые слова. Это похоже на Кодирование Фибоначчи, за исключением того, что он позволяет представлять как положительные, так и отрицательные целые числа. Все коды заканчиваются на «11» и не имеют «11» в конце.
Код Фибоначчи тесно связан с представление negaFibonacciпозиционный система счисления иногда используется математиками. Код negaFibonacci для конкретного ненулевого целого числа в точности совпадает с кодом представления negaFibonacci целого числа, за исключением того, что порядок его цифр изменен на противоположный, и в конце добавлена дополнительная «1». Код НегаФибоначчи для всех отрицательных чисел состоит из нечетного числа цифр, а для всех положительных чисел - из четного числа цифр.
Вычислить наибольшее (или наименьшее) кодируемое число с помощью N бит путем суммирования нечетных (или четных) Негафибоначчи числа от 1 до N.
Когда будет установлено, что N бит достаточно, чтобы содержать Икс, вычтите Nth число negaFibonacci из Икс, отслеживая остаток, и поместите единицу в Nth бит вывода.
Работая вниз от Nth бит с первым, сравните каждое из соответствующих чисел негаФибоначчи с остатком. Вычтите его из остатка, если абсолютное значение разницы меньше, И если в следующем более высоком бите еще нет единицы. Единица помещается в соответствующий бит, если выполняется вычитание, или ноль, если нет.
Поместите один в N + 1-й немного закончить.
Чтобы декодировать токен в коде, удалите последнюю «1», присвойте оставшимся битам значения 1, -1, 2, -3, 5, -8, 13… ( Negafibonacci числа) и сложите биты "1".
Кнут, Дональд (2008), Числа Негафибоначчи и гиперболическая плоскость, Доклад, представленный на ежегодном собрании Математической ассоциации Америки, Сан-Хосе, Калифорния..
