2
$\begingroup$

Why do most programming languages (if not all) lack a 2-bit data type?

A boolean is a single bit with the values being either true or false.

Why is there no native, corresponding type where the values can be either true, false, neither or both? This data type can of course be constructed inside the language, but I figure there would be lots of usages for a more fundamental language support for it.

This data type would be very handy in, for instance:

  • gene programming (values being: A, C, G or T)
  • GUI programming (a checkbox that is: not checkable, unchecked, checked, or both/unknown)
  • testing (test result can be: not run, pass, fail or inconclusive)
  • quantum programming (values being: true, false, neither or both)

Is there a scientific reason to why this data type (quad, qool, qit etc.) has been excluded?

$\endgroup$
9
  • $\begingroup$ Because in general, processors do not handle single bit values, they handle at least full bytes at a time. In C++ for example, the sizeof(bool) is 1 byte, even though it only has two possible values. $\endgroup$
    – Geier
    Mar 23, 2013 at 17:55
  • 6
    $\begingroup$ Note that C and related languages support bitfields, making it relatively easy to define a 2 bit data type. $\endgroup$
    – Paul R
    Mar 23, 2013 at 17:57
  • 3
    $\begingroup$ It sounds like in many of the proposed use cases, an enumeration is appropriate. The compiler could then choose how to store and optimize use of such. Tiny integers are less broadly supported. $\endgroup$
    – user4577
    Mar 23, 2013 at 23:35
  • 2
    $\begingroup$ Note that the qubits of quantum computers are far more complicated than simply "true, false, neither, or both." A single qubit (in a pure state), when measured, has some probability p of being measured as 0 and probability 1 - p of being measured as 1. However, qubits really get interesting with entanglement: two qubits can be related in such a way that they can't be separated into pure states. This means that representing a two-qubit system is harder than representing two qubits! (In general, you need exponential, not linear, classical space.) $\endgroup$ Mar 25, 2013 at 5:01
  • 2
    $\begingroup$ What would qualify as "scientific reason"? Not that there is not even a scientific reason for using binary (that I am aware of). $\endgroup$
    – Raphael
    Mar 25, 2013 at 10:06

6 Answers 6

6
$\begingroup$

Like Geier said, processors can't directly handle values smaller than a byte. So a boolean type that was actually implemented as just a single bit would in most cases be inefficient. The processor needs to do a bit of extra work to extract just that one bit.

The reason that the boolean type exists is more about semantics than anything else. Logical true/false values is a very useful concept. In many programming languages a conditional expression like "if x is 5" has a boolean value as the result. And lets not forget that a boolean type corresponds nicely to a single bit, which is the building block of the binary numbers that computers work with.

There has been tri-state "booleans" in use, and there probably still is today. But they are generally less useful and more complicated to deal with than the ordinary true/false ones.

What you are talking about would generally be implemented as bit flags (or bit fields), or simply by assigning different meanings to different numbers.

$\endgroup$
1
  • 2
    $\begingroup$ Some processors (generally for microcontrollers) can directly access bits either by explicit instructions (MIPS MCU Application Specific Extension supplies such) or by bit-band memory regions where ordinary memory accesses become bit accesses (ARM supports this feature). I think some 8-bit processors might also support bit memory accesses. $\endgroup$
    – user4577
    Mar 23, 2013 at 23:38
3
$\begingroup$

The reason is that architectures offer the types most often used. If you look at real programs, they handle characters (mostly implemented as 8 bit bytes), much more often integers (for array indices, much computation, things like file sizes). Approximations for real numbers are also important. Boolean values as such are very rarely handled (most conditions are handled as conditions in the CPU, and by conditional jumps). If you look at the types offered by C, they are a close match to the above. To give boolean values, the convention is that a zero value or a NULL pointer is false, as checking for those values is common.

Then there is the consideration of making shuffling values from/to memory has to be efficient, and current architectures live and die by their caches, which move multiple words at a time. Adding paths inside the CPU for handling another data size is costly too.

An extreme case of C weirdness was the CRAY, in which even characters where 32 bits, in the interests of maximal performance.

$\endgroup$
2
$\begingroup$

As well as the other answers that have been given, consider that it's not obvious what the basic operations on two-bit data types should be.

If you have two boolean values and want to combine them somehow, there are exactly 16 possible functions. Six of these are degenerate (i.e. they are constants or unary functions in disguise), leaving 10. They are:

  • and
  • or
  • exclusive or
  • left-implication
  • right-implication

and the negations of these (nand, nor etc). The implications and their negations are trivially implementable in terms of negation and and/or, so you only need three. This is a tractable number. Hell, even ten is a reasonably tractable number of operations to provide if you can think up good names for them.

For two-bit data types it's far from obvious what most of the operations are useful for, and how they should be used, and it depends far more on what precisely the values mean.

For DNA, for example, one of the workhorse operations is reverse complement, which is only useful on a vector of nucleotides.

But if your values are the full lattice completion of a two-element domain (let's call them $\bot$, $0$, $1$ and $\top$), the interesting operations are join and meet. If it's the Klein four-group, then you want the group operations. If it's $GF(4)$, then you want field operations.

The abstract operations that the two-bit data type should provide are too tied to what the values mean, and there are too many of them ($2^{16}$ binary operations, admittedly including degenerate ones but were still talking "thousands" rather than "several") to provide them all.

Real data types are not just sets of values, they also have an internal structure. It's the structure which makes them complex. If it was just a matter of providing a set of values, then your favourite programming language or library could easily give it to you as an abstraction on top of the physical machine. But there are so many possibilities, that it's not clear what you specifically want.

If it is clear what structure you specifically want, then you don't want a type, you want a library.

$\endgroup$
2
$\begingroup$

Because it is not as useful to define it as a basic data type in general purpose programming language. In designing programming language it is important to keep the core language simple and small. Just because it has some applications doesn't make it essential for the core of a general purpose language, if every time someone used some data type we included in the core of a general purpose language then it would become too complicated and heavy. For such non-essential data types most general purpose programming languages provides easy ways of define them as a non-basic data type. For example, in C/C++ you can use the enum data type to implement a data type with a finite set of values.

On the other hand, Boolean data type is general and essential enough to be included in the core of most general purpose language. The conditional statements depend on it, the computer hardware depends on it, etc. So it is natural to include it as a basic data type in the core of these languages.

$\endgroup$
1
$\begingroup$

To understand why languages don't have a double-bit type, it may be helpful to consider why they have Boolean. Generally it's not because working with Boolean values is more efficient than working with integers, but rather because, with integers, even if a!=0 and b!=0 it's possible that (a & b)==0. If a and b are expressions which will always be either zero or one, the statements if (a & b) ... will be equivalent to both if ((a != 0) & (b != 0)) ... and if ((a & b) != 0) .... If, however, the expressions may yield other values, then the two latter forms would not be equivalent to each other. If the intention had been to ensure that neither a nor b was zero, but the variables could in fact hold different non-zero values which have no overlapping bits, the expression which worked fine when a and b had to be zero or one would break. Requiring that integer values be cast to Boolean before being used in a conditional context compels the programmer to specify which of two plausible meanings was intended.

The fact that an if statement executes something or doesn't, and a loop likewise repeats or doesn't, creates an inherent need for a two-state conditional. While there may be some cases where a three-way or four-way branching construct would be helpful, most such needs are handled perfectly adequately by an n-way branching structure such as switch. Absent a particular reason to favor three-way and four-way branching over arbitrary branching, a two-bit type wouldn't really serve much purpose.

$\endgroup$
0
$\begingroup$

Added in response to link from why programming languages don't have types smaller than byte:

Writing a value which is narrower than a system's memory bus requires that a processor must do one of two things:

  1. Read an entire word, update part of it, and write the whole thing back.

  2. Output the part of the word that should change, while disabling the chips holding the parts of the word that shouldn't change.

Approach #2 will be generally be faster than approach #1 when it is feasible, but requires adding circuitry to implement. Early reprogrammable microcomputers had an 8-bit bis and did not include any signals to disable part of it; when later microcomputers used a 16-bit bus, including enough circuitry to independently enable and disable two halves of it was a burden, but it made it much easier to work with code that had been written for 8-bit systems. Allowing data to be written in 4-bit chunks would have required adding twice as much circuitry, without yielding a huge amount of additional benefit. When bus widths expanded to 32 bits, the amount of support circuitry doubled, but so did the maximum data throughput.

Thus, on most systems as constructed, writing a fraction of a byte would take twice as long as writing an entire byte; while it would be possible to build hardware to allow smaller writes, the benefits would fall short of the extra costs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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