Loading AI tools
From Wikipedia, the free encyclopedia
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.
![]() | This section contains instructions, advice, or how-to content. (September 2022) |
To encode a nonzero integer X:
To decode a token in the code, remove the last "1", assign the remaining bits the values 1, −1, 2, −3, 5, −8, 13... (the negafibonacci numbers), and add the "1" bits.
Negafibonacci coding is closely related to negafibonacci representation, a positional numeral system sometimes used by mathematicians. The negafibonacci code for a particular nonzero integer is exactly that of the integer's negafibonacci representation, except with the order of its digits reversed and an additional "1" appended to the end. The negafibonacci code for all negative numbers has an odd number of digits, while those of all positive numbers have an even number of digits.
The code for the integers from −11 to 11 is given below.
Number | Negafibonacci representation | Negafibonacci code |
---|---|---|
−11 | 101000 | 0001011 |
−10 | 101001 | 1001011 |
−9 | 100010 | 0100011 |
−8 | 100000 | 0000011 |
−7 | 100001 | 1000011 |
−6 | 100100 | 0010011 |
−5 | 100101 | 1010011 |
−4 | 1010 | 01011 |
−3 | 1000 | 00011 |
−2 | 1001 | 10011 |
−1 | 10 | 011 |
0 | 0 | (cannot be encoded) |
1 | 1 | 11 |
2 | 100 | 0011 |
3 | 101 | 1011 |
4 | 10010 | 010011 |
5 | 10000 | 000011 |
6 | 10001 | 100011 |
7 | 10100 | 001011 |
8 | 10101 | 101011 |
9 | 1001010 | 01010011 |
10 | 1001000 | 00010011 |
11 | 1001001 | 10010011 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.