I matematik är negafibonacci-kodning en universell kod som kodar heltal som inte är noll till binära kodord . Det liknar Fibonacci-kodning , förutom att det tillåter att både positiva och negativa heltal representeras. Alla koder slutar med "11" och har ingen "11" före slutet.
Beräkna det största (eller minsta) kodningsbara talet med N bitar genom att summera de udda (eller jämna) negafibonaccitalen från 1 till N .
När det har fastställts att N bitar är precis tillräckligt för att innehålla X , subtrahera det N:te negafibonacci-talet från X , håll reda på resten, och sätt en etta i den N:te biten av utdata.
Arbeta nedåt från den N:e biten till den första, jämför vart och ett av de motsvarande negafibonacci-talen med resten. Subtrahera det från resten om det absoluta värdet av skillnaden är mindre, OCH om nästa högre bit inte redan har en etta i sig. En etta placeras i lämplig bit om subtraktionen görs, eller en nolla om inte.
Lägg en etta i N+1: e biten för att avsluta.
För att avkoda en token i koden, ta bort den sista "1", tilldela de återstående bitarna värdena 1, −1, 2, −3, 5, −8, 13... (negafibonacci-talen), och lägg till " 1" bitar.
Negafibonacci-kodning är nära släkt med negafibonacci-representation , ett positionsnummersystem som ibland används av matematiker. Negafibonacci-koden för ett visst heltal som inte är noll är exakt koden för heltalets negafibonacci-representation, förutom med omvänd ordning på dess siffror och ytterligare en "1" tillagd i slutet. Negafibonacci-koden för alla negativa tal har ett udda antal siffror, medan de för alla positiva tal har ett jämnt antal siffror.
