29

I am going to teach a small group of people about the numbering systems in computing and was wondering how many bits per digit are there in the decimal system, for instance:

  • Hex (base 16) - 4 bits
  • Octal (base 8) - 3 bits
  • Binary (base 2) - 1 bit
  • Decimal (base 10) - ?
  • 7
    Intuition: Let's say what you seek is d, it covers one decimal digit, the range of 0..9. 3*d bits mean three decimal digits and allow you to represent integers from the range 0..999. Whole ten bits (think binary now) give a range of 0..1023. 999 is quite close to 1023, yet a little less. So you may expect d should be little less than 10/3. – Kamil Maciorowski Nov 28 '17 at 11:31
  • 5
    This post seems like it would fit better on Stack Overflow than on Super User. – gmarmstrong Nov 28 '17 at 11:39
  • 21
    @gmarmstrong: I'd argue Mathematics.SE (or possibly SoftwareEngineering.SE). This is not directly related to a programming problem. – Flater Nov 28 '17 at 14:28
  • 10
    @Flater: Mathematics is definitely the right place, as this is basically information theory 101. – MechMK1 Nov 28 '17 at 15:55
  • 7
    There’s no shame in not knowing this, but one who doesn’t might not be the best person for teaching number systems. – WGroleau Nov 28 '17 at 17:59

10 Answers 10

98

What you are looking for is the 2-based logarithm of 10, which is an irrational number of around 3.32192809489....

The fact that you can't use an integer number of bits for a decimal digit is the root cause of why many fractions that are easy to express in the decimal system (e.g. 1/5 or 0.2), are impossible (not hard: really impossible) to express in binary. This is important when evaluating rounding errors in floating point arithmetics.

20

In other words, what amount of information is contained in a single digit in these systems.

For base 2, base 4, base 8, base 16 and other 2N bases the answer is obvious because in a base 2N each digit can be expressed with exactly N digits.

How do you get N given 2N? Well, you use a 2-based logarithm, which is an inverse of exponentiation.

  • log2 2 = 1 (1 bit per digit in base 2)
  • log2 4 = 2 (2 bits per digit in base 4)
  • log2 8 = 3 (3 bits per digit in base 8)
  • log2 16 = 4 (4 bits per digit in base 16)

K-based logarithms of numbers that are not powers of K aren't cardinal numbers. In particular:

  • log2 10 = 3.321928094887362347870319429489390175864831393024580612054…

This number may look confusing, but it actually has some uses. For example, it's an entropy of a single decimal digit.

For your case, though, I don't think this value is of any use. @Christian's answer does a good job at explaining why.

8

On the subject of bits:

I'm sorry to say the question is misguided. You wouldn't use bits in that manner. A bit is a binary digit. You can convert the decimal number 10, to a binary 1010 (8+2), so you'd need 4 bits to express the decimal value 10.


Powers of 2

You've fallen into a bit of a trap, by using binary (2), octal (8) and hexadecimal (16) as examples, because these are all powers of 2, and thus you can think of them in terms of bits, whereas 10 isn't a power of 2, so it just doesn't work very well like that.

  • 18
    The question is not misguided. In the subject of information theory it is perfectly normal to talk about bits in this way. And then Eugen Rieck's answer is a good answer. – user831198 Nov 28 '17 at 12:12
  • 2
    I suggest that you mention BCD (binary-coded decimal), which is commonly represented by 4-bits in electronics. In practical terms, the number of bits used to represent a decimal number is typically 4, but it depends upon the implementation. – davidmneedham Nov 28 '17 at 14:42
  • 1
    @DavidStockinger Right, it depends on whether it is a theoretical question or an implementation question. – davidmneedham Nov 28 '17 at 15:49
  • 2
    ln(10)/ln(2) is the theoretical answer. 4 bits is the likely implementation answer. – davidmneedham Nov 28 '17 at 15:59
  • 2
    @davidmneedham No, most numbers are stored in binary. BCD is used for rare specialised purposes but most encodings are either integer or floating point decimal. In these systems the log answer is the correct one, it gives minimum number of bits to store all numbers of a given decimal length (round up) and explains why a given number of bits does not store a fixed number of decimal digits. – Jack Aidley Nov 29 '17 at 12:49
7

BCD - Binary Coded Decimal uses 4 bits per digit, the same as Hexadecimal.

https://en.wikipedia.org/wiki/Binary-coded_decimal

  • Except that "BCD" is often used to refer to the 6-bit character encoding. – Daniel R Hicks Nov 30 '17 at 2:46
  • @DanielRHicks Ah, OK. Wikipedia says that it was used the late 1950s and early 1960s (i.e. before EBCDIC was invented), so I'm not ashamed I never heard of it. Even though I now realise that the name EBCDIC was derived from it! Anyway, the term BCD is not still "often used" to refer to the encoding as you're saying. – Mr Lister Dec 6 '17 at 14:21
3

Using bits implies a power of 2, thus, as others have said you can't easily shohorn 10 bits into bytes without wastage. A common solution is to use 4 bits as per hexadecimal and waste the 6 states represented as A-F. The interesting bit is doing decimal math with this - it's not neat and simple.

A useful teaching idea might be to compare how Micky Mouse might have developed a counting system, as he only has 4 fingers per hand - which leads naturally to an octal based system.

  • I believe you meant to refer to Hex in your answer as its Hex that has the A-F values – user92592 Nov 28 '17 at 11:42
  • @user92582 yes, ta. Corrected. – davidgo Nov 28 '17 at 11:44
  • And you can use those "waste" 6 states to encode a decimal point, negative, sequence terminator, etc. As for decimal math... it's not neat but simple? Just write some code to do what we teach little children :p – Kaithar Nov 28 '17 at 18:22
  • @kaithar - I don't believe that what you are proposing is valid, as any one of those operations would require a full bit or more - which you don't have available. – davidgo Nov 28 '17 at 18:25
  • 1
    No ideaal where the "10 bits" are coming form. 10 bits =1024 values. A decimal digit only has 10 possible values. – MSalters Nov 29 '17 at 19:57
3

This might be an oversimplification but it depends on which question you are asking.
(and the answer is basically octal or hex)

I also don't consider fractional bits as bits because in practical usage bits don't have fractions.

Q1: How many bits can you represent in a decimal digit?

A1: You can represent 3 bits of information in a single decimal digit:

The most common scheme would be straight binary with wrapping where 0=8=000 and 1=9=001. But you could use any scheme there is nothing that says this is the only way to encode bits into decimal digits.

  • 0: 000
  • 1: 001
  • 2: 010
  • 3: 011
  • 4: 100
  • 5: 101
  • 6: 110
  • 7: 111
  • 8: 000 <- wrapping (or unused)
  • 9: 001 <- wrapping (or unused)

or

Q2: How many bits does it take to represent a decimal digit?

A2: You need at least 4 bits to represent all decimal digits. With some waste or wrapping.

Again the most common scheme would be straight binary with wrapping but you could use any other scheme.

  • 0: 0000
  • 1: 0001
  • 2: 0010
  • 3: 0011
  • 4: 0100
  • 5: 0101
  • 6: 0110
  • 7: 0111
  • 8: 1000
  • 9: 1001
  • 0: 1010 <- wrapping (or unused)
  • 1: 1011 <- wrapping (or unused)
  • 2: 1100 <- wrapping (or unused)
  • 3: 1101 <- wrapping (or unused)
  • 4: 1110 <- wrapping (or unused)
  • 5: 1111 <- wrapping (or unused)
2

In base 1024, each symbol is 10 bits. Three decimal digits have the same amount of information as one digit in base 1000, which is slightly less than 1024. Therefore, a decimal digit has slightly less than 10/3 bits. This approximation gives 3.333333..., while the exact number is 3.321928...

2
  • Hex (base 16) - 4 bits
  • Octal (base 8) - 3 bits
  • Binary (base 2) - 1 bit
  • Decimal (base 10) - 3 1/3 bits.
    210 = 1,024
    103 = 1,000
    220 = 1,048,576
    106 = 1,000,000
    3 digits in base 10 up to 999 can be held in 10 bits in base 2.
    6 digits in base 10 up to 999,999 can be held in 20 bits in base 2.
    This is were the idea of kilobytes, megabytes, and gigabytes originated.
  • It's actually slightly less than 3 1/3... Your answer is a bit ambiguous, and the suggestion that numbers up to 999 can be stored instead of numbers between 0-1023 is a bit misleading. – wizzwizz4 Nov 29 '17 at 21:53
0

Disclaimer - I'm not an information theorist, just a code monkey who works primarily in C and C++ (and thus, with fixed-width types), and my answer is going to be from that particular perspective.

It takes on average 3.2 bits to represent a single decimal digit - 0 through 7 can be represented in 3 bits, while 8 and 9 require 4. (8*3 + 2*4)/10 == 3.21.

This is less useful than it sounds. For one thing, you obviously don't have fractions of a bit. For another, if you're using native integer types (i.e., not BCD or BigInt), you're not storing values as a sequence of decimal digits (or their binary equivalents). An 8 bit type can store some values that take up to 3 decimal digits, but you can't represent all 3-decimal-digit values in 8 bits - the range is [0..255]. You cannot represent the values [256..999] in only 8 bits.

When we're talking about values, we'll use decimal if the application expects it (e.g., a digital banking application). When we're talking about bits, we'll usually use hex or binary (I almost never use octal since I work on systems that use 8-bit bytes and 32-bit words, which aren't divisible by 3).

Values expressed in decimal don't map cleanly on to binary sequences. Take the decimal value 255. The binary equivalents of each digit would be 010, 101, 101. Yet, the binary representation of the value 255 is 11111111. There's simply no correspondence between any of the decimal digits in the value to the binary sequence. But there is a direct correspondence with hex digits - F == 1111, so that value can be represented as FF in hex.

If you're on a system where 9-bit bytes and 36-bit words are the norm, then octal makes more sense since bits group naturally into threes.


  1. Actually, the average per digit is smaller since 0 and 1 only require a single bit, while 2 and 3 only require 2 bits. But, in practice, we consider 0 through 7 to take 3 bits. Just makes life easier in a lot of ways.

  • 4
    It's not quite that simple; for example, that 3-or-4 bit encoding isn't sufficient to tell whether 1001001 should be 91 or 49. – user409120 Nov 28 '17 at 21:00
  • @Hurkyl: again, my perspective is using fixed-width integer types - 1001001 maps to 73 (64 + 8 + 1). I do not interpret it as a sequence of binary coded decimal digits. If it's supposed to be BCD, which must use 4 bits per digit, then we must assume a leading 0 bit, so it must be 49. – John Bode Nov 28 '17 at 21:16
  • 2
    I was just trying to point out that variable-length encodings aren't as simple as you make them out to be; you need to tell where one symbol ends and another begins. so you can't just say that you can represent 8 and 9 with four bits, 4-7 with three, 2-3 with two and 0-1 with one. And you can see that the 3.2 figure you get actually violates the information theory bound of log(10)/log(2). – user409120 Nov 28 '17 at 21:24
  • @Hurkyl: I wasn't trying to make anything simple, nor was I talking about any sort of encoding. The largest value that can be represented in a 32-bit integer is 10 decimal digits wide (3.2 bits per digit), but there's no correspondence between the binary encoding of any of the digits and the binary encoding of the value. If you're using some form of binary coding for decimal digits, then either the width must be fixed a la BCD, or you must use some kind of Huffman coding, which I am not advocating. – John Bode Nov 28 '17 at 22:05
  • 1
    The problem with this scheme is that you forgot the one extra bit you need to indicate whether 3 or 4 bits follow. And with an average length of 4.2 bits per decimal digit, this is even worse than BCD – MSalters Nov 29 '17 at 20:01
0

If I were teaching this, I would first explain what a number (expressed as a series of digits means). i.e., from right to left, assuming base n, a * n^0 + b * n^1 + c * n ^2 ... z * n^y.

Then explain that 10^3 is approximately equal to 2 ^ 10. It is not exact and is the reason in computers, we often do not know what 2k really means (is it 2,000 or 2,048?) It serves fairly well for quick approximations. 2^16 is about 2 ^ (16 - 10) * 1,000, or 2^6 (64) * 1,000 or 64,000. In reality, it is 65,536, but if you don't mind being off around a percent, it works fairly well for quick approximations.

  • While this is a clever insight and a valuable contribution to the OP’s course curriculum, it is not an answer to the question. – Scott Nov 30 '17 at 14:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.