World Library  
Flag as Inappropriate
Email this Article

Skew binary number system

Article Id: WHEBN0030537795
Reproduction Date:

Title: Skew binary number system  
Author: World Heritage Encyclopedia
Language: English
Subject: Three-valued logic, Non-standard positional numeral systems, Ternary computer, Linked list, Number theory
Publisher: World Heritage Encyclopedia

Skew binary number system

The skew binary number system is a non-standard positional numeral system in which the nth digit has a value of 2^{n+1} - 1 and each digit has a value of 0, 1, or 2. Each number can be written uniquely in skew binary canonical form where there is only at most one instance of the digit 2, which must be the first non-zero least significant digit, as shown in following table:

Decimal Skew binary binary
0 0 0
1 1 1
2 2 10
3 10 11
4 11 100
5 12 101
6 20 110
7 100 111
8 101 1000
9 102 1001
10 110 1010
11 111 1011
12 112 1100
13 120 1101
14 200 1110
15 1000 1111

The advantage of skew binary is that each increment operation can be done with at most one carry operation. This exploits the fact that 2 (2^{n+1} - 1) + 1 = 2^{n+2} - 1 . Incrementing a skew binary number is done by setting the only two to a zero and incrementing the next digit from zero to one or one to two.[1]

Skew binary numbers find applications in skew binomial heaps, a variant of binomial heaps that support worst-case O(1) insertion, and in skew binary random access lists, a purely functional data structure. They also find use in bootstrapped skew binomial heaps, which have excellent asymptotic guarantees.[2]

See also


  1. ^ skew binary numbers
  2. ^ Okasaki, Chris. Purely Functional Data Structures.

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.