Negafibonacci coding

In mathematics, negafibonacci coding is a universal code which encodes nonzero integers into binary code words. It is similar to Fibonacci coding, except that it allows both positive and negative integers to be represented. All codes end with "11" and have no "11" before the end.

In mathematics, negafibonacci coding is a universal code which encodes nonzero integers into binary code words. It is similar to Fibonacci coding, except that it allows both positive and negative integers to be represented. All codes end with "11" and have no "11" before the end. If x is positive, compute the greatest odd negative integer n such that the sum of the odd negative terms of the negafibonacci sequence from −1 to n with a step of −2, is greater than or equal to x : n \in \{ - \left( 2k + 1 \right) , k \in [0, \infty [ \} , \quad \sum_{i=-1, \; i \; odd}^{n-2} f(i) If x is negative, compute the greatest even negative integer n such that the sum of the even negative terms of the negafibonacci sequence from 0 to n with a step of −2, is less than or equal to x : n \in \{ - 2k , k \in [2, \infty [ \} , \quad \sum_{i=-2, \; i \; even}^{n-2} f(i) > x \geq \sum_{i=-2, \; i \; even}^{n} f(i) Add a 1 at the |n|^{\text{th}} bit of the binary word. Subtract f(n) from x . Repeat the process from step 1 with the new value of x, until it reaches 0. Add a 1 on the left of the resulting binary word to finish the encoding. To decode an encoded binary word, remove the leftmost 1 from the binary word, since it is used only to denote the end of the encoded number. Then assign the remaining bits the values of the negafibonacci sequence from −1 (1, −1, 2, −3, 5, −8, 13...), and sum the all the values associated with a 1.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1362628415 under CC BY-SA 4.0; modifications have been made.