Dual system

 Decimal numbers 0 to 15 in the dual system Valence: 8 4 2 1 Zero: 0 0 0 0 One: 0 0 0 1 Two: 0 0 1 0 Three: 0 0 1 1 Four: 0 1 0 0 Five: 0 1 0 1 Six: 0 1 1 0 Seven: 0 1 1 1 Eight: 1 0 0 0 Nine: 1 0 0 1 Ten: 1 0 1 0 Eleven: 1 0 1 1 Twelve: 1 1 0 0 Thirteen: 1 1 0 1 Fourteen: 1 1 1 0 Fifteen: 1 1 1 1

The dual system ( lat. Dualis "containing two"), also called the two-part system or binary system , is a number system that uses only two different digits to represent numbers .

In the usual decimal system , the digits 0 to 9 are used. In the dual system, however, numbers are only represented with the digits of the value zero and one . The symbols 0 and 1 are often used for these digits . Numbers zero through fifteen are listed on the right.

The dual system is the place value system with base 2, so it provides the dyadic (2-adic) representation of numbers ( dyadic ) ( gr. Δύο = two ).

Due to its importance in digital technology , it is the most important number system alongside the decimal system.

The number representations in the dual system are also called dual numbers or binary numbers . The latter is the more general name, as it can simply stand for binary-coded numbers . The term binary number does not specify the way a number is represented, it only states that two different digits are used.

Definition and representation

In the case of numbers in the dual system, the digits are written one after the other without separators, as in the commonly used decimal system, but their place value corresponds to the power of two and not the power of ten. ${\ displaystyle z_ {i}}$

The most significant digit with the value is written on the far left and the lower significant digits with the values up to the right of it in descending order. To represent rational or real numbers , a separating comma is followed by the digits to , which represent the fraction of the number. If this display stops, it looks like this: ${\ displaystyle z_ {m}}$${\ displaystyle z_ {m-1}}$${\ displaystyle z_ {0}}$${\ displaystyle z _ {- 1}}$${\ displaystyle z _ {- n}}$

${\ displaystyle z_ {m} z_ {m-1} \ ldots z_ {0} \ operatorname {,} z _ {- 1} z _ {- 2} \ ldots z _ {- n} \ qquad \ left (m, n \ in \ mathbb {N} \ quad z_ {i} \ in \ {0,1 \} \ right)}$

The value of the binary number results from adding these digits, which are multiplied by their place value beforehand: ${\ displaystyle Z}$${\ displaystyle 2 ^ {i}}$

${\ displaystyle Z = \ sum _ {i = -n} ^ {m} z_ {i} \ cdot 2 ^ {i}}$.

The symbols 0 and 1 are usually used to represent the two digits, analogous to other number systems.

In older literature related to electronic computing , the symbols Low (L) and High (H) are sometimes used in place of 0 and 1. Low then usually stands for the value zero and high for the value one. This assignment is called positive logic , with negative logic the values ​​are assigned the other way round. In computer science, the "digits" true (w) and false (f) or the English translations true (t) and false (f) are also used for binary coded values , whereby false = 0 and true = 1 are usually set.

The symbols L for the value one and 0 for the value zero are (rarely) used.

Negative numbers are written in the binary system as in the decimal system with a preceding minus (-).

Examples

The sequence of digits 1101, for example, does not represent the thousand one hundred and one (as in the decimal system), but the thirteen, because in the dual system the value is calculated through

${\ displaystyle [1101] _ {2} = 1 \ cdot 2 ^ {3} +1 \ cdot 2 ^ {2} +0 \ cdot 2 ^ {1} +1 \ cdot 2 ^ {0} = [13] _ {10}}$

and not through as in the decimal system

${\ displaystyle 1 \ cdot 10 ^ {3} +1 \ cdot 10 ^ {2} +0 \ cdot 10 ^ {1} +1 \ cdot 10 ^ {0} = [1101] _ {10}}$.

For further techniques and examples for converting binary numbers into decimal numbers and vice versa: see section Converting binary numbers into other place value systems .

The bracketing of the results with the subscript 2 or the 10 indicates the basis of the value system used . This makes it easy to see whether the number is displayed in the dual or decimal system. In the literature, the square brackets are often left out and the subscript is sometimes put in round brackets. It is also possible to identify it by adding the capital letter B (for binary ).

Different ways of writing the number twenty-three in the dual system:

• [10111] 2
• 10111 2
• 10111 (2)
• 10111b (so-called Intel Convention)
• 10111B
• 0b10111
• % 10111 (so-called Motorola convention, but also e.g. with DR-DOS DEBUG )
• HLHHH
• L0LLL

history

Development of the dual system

The ancient Indian mathematician Pingala provided the first known description of a number system consisting of two characters in the 3rd century BC. BC before. However, this number system did not have a zero.

A series of eight trigrams and 64 hexagrams are known from the ancient Chinese and Daoist text I Ching . In the 11th century, the Chinese scholar and philosopher Shao Yong developed a systematic arrangement of hexagrams, representing the sequence from 1 to 64, and a method for producing the same. However, there is no evidence that Shao knew how to make calculations in the dual system or that he recognized the concept of value.

Joachim Bouvet transmitted the sixty-four hexagrams from China to Leibniz , 1701

Centuries before the dual system was developed in Europe, Polynesians used binary summaries of numbers to simplify calculations.

At the end of the 17th century, Gottfried Wilhelm Leibniz already felt the dyadic (dyo, Greek = two), i.e. the representation of numbers in the dual system, which he developed, was very important. He saw it as such a convincing symbol of the Christian faith that he wanted to convince the Chinese Emperor Kangxi with it. He wrote to the French Jesuit priest Joachim Bouvet (1656–1730):

“At the beginning of the first day it was 1, which means God. At the beginning of the second day the 2, because heaven and earth were created during the first. Finally at the beginning of the seventh day everything was already there; therefore the last day is the most perfect and the Sabbath , because on it everything is created and fulfilled, and therefore the 7 111 is written, i.e. without a zero. And only if you just write the numbers with 0 and 1, you can see the perfection of the seventh day, which is considered sacred, and of which it is also noteworthy that its characters are related to the Trinity . "
The binary number system in a first draft by Gottfried Wilhelm Leibniz, 1697

On the other hand, his description in a letter to Duke Rudolf von Braunschweig-Wolfenbüttel on January 2, 1697 was somewhat more secular:

“... For one of the main points of the Christian faith ... is the creation of all things out of nothing by the omnipotence of God. Now one can say that nothing in the world represents this better than the origin of the numbers, as it is presented here, by expressing them only with one and zero (or nothing). It will be difficult to find a better example of this mystery in nature and philosophy ... This is all the more fitting because the empty depths and desolate darkness belong to zero and nothing, but the spirit of God with its light belongs to the almighty one. Because of the words of the symbol I thought for a while and finally found this verse to be good: To develop everything from nothing is enough for one (Omnibus ex nihilo ducendis sufficit unum). "

Probably because the precision mechanical skills of the time were insufficient, Leibniz resorted to the decimal system when building his calculating machines .

Page from “Explication de l'Arithmétique Binaire” , 1703

The dual system was fully documented by Leibniz at the beginning of the 18th century in his article Explication de l'Arithmétique Binaire (Histoire de l'Academie Royale des Sciences 1703, published in Paris 1705). Leibniz also confirms the view of Joachim Bouvet , a missionary at the Chinese imperial court, who interpreted the tri- and hexagrams of Fu Hsi (see figure : "Signs of Fu Hsi") as numerals in a certain reading direction. He saw it as an archaic binary system that has been forgotten. This interpretation is now considered very unlikely.

Leibniz also had predecessors in Europe. An earlier treatment of the dual system and other position systems by Thomas Harriot was not published by Thomas Harriot , but was only found in the estate. The first publication of the dual system in Europe is probably in Mathesis Biceps vetus et nova 1670 by the later Spanish bishop Juan Caramuel y Lobkowitz (1606–1682), who also deals with numbers for other bases. Also Blaise Pascal noticed already in De numeris multiplicibus (1654, 1665) that the base 10 is not a necessity.

In 1854, the British mathematician George Boole published a seminal paper detailing a system of logic that became known as Boolean algebra . His logical system paved the way for the realization of electronic circuits that implement arithmetic in the dual system.

application

The dual system became very important in the development of electronic calculating machines, because in digital technology, numbers are represented by electrical states. Two complementary states such as current on / current off or voltage / ground are preferably used, since in this way very error-resistant and simple circuits can be implemented (see binary code ). These two states can then be used as digits. The dual system is the easiest way to calculate with numbers that are represented by these two digits.

Binary numbers are used in electronic data processing to represent fixed-point numbers or whole numbers . Negative numbers are mainly represented as two's complement , which only corresponds to the dual number representation in the positive area. The one's complement , which corresponds to the inverted representation of binary numbers with a preceding one, is used less often. Representing negative numbers in one's complement has the disadvantage that there are two representations for zero, one in the positive and one in the negative. The excess code based on a value range shift offers a further alternative .

In order to approximately represent rational or even real numbers with non-terminating binary number representation in electronic data processing, floating point representations are preferably used in which the number is normalized and divided into mantissa and exponent . These two values ​​are then stored in the form of binary numbers.

Calculation of required places

A binary number with digits can have the maximum value . A four-digit binary number can therefore have at most the value , i.e. 16 - 1 = 15. ${\ displaystyle n}$${\ displaystyle 2 ^ {n} -1}$${\ displaystyle 2 ^ {4} -1}$

Consequently, in the dual system, you can count up to 1023 with your 10 fingers . ${\ displaystyle 2 ^ {10} -1}$

In digital technology, it should be noted that when a binary number is saved, its sign must also be saved. In most cases, the most significant bit in the memory area reserved for the number is used for this purpose. If this memory area is bit large, the maximum value of the positive numbers and the minimum value of the negative numbers are (when the negative numbers are represented in two's complement ) . This is one of the positive numbers and that is the "first negative number". Overall, the number of numbers that can be displayed remains the same . ${\ displaystyle n}$${\ displaystyle 2 ^ {(n-1)} - 1}$${\ displaystyle - (2 ^ {(n-1)})}$${\ displaystyle 0}$${\ displaystyle -1}$${\ displaystyle 2 ^ {n}}$

The number of digits required in the binary system for a given number in the decimal system is ${\ displaystyle n}$

${\ displaystyle \ lfloor \ operatorname {lb} n \ rfloor +1}$.

In this case, referred to the rounding function and the base-2 logarithm of the number . Alternatively, the number of decimal places can be multiplied by 3.322 (+ rounding up), which results in an upper limit, because (one decimal place, actually lb ( ) becomes a maximum of binary places). ${\ displaystyle \ lfloor \ cdot \ rfloor}$${\ displaystyle \ operatorname {lb} n}$${\ displaystyle n}$${\ displaystyle lb (10) \ approx 3 {,} 322}$${\ displaystyle 9 {,} {\ bar {9}}}$${\ displaystyle \ approx 3 {,} 322}$

Basic arithmetic in the dual system

Analogous to the numbers in the decimal system , the common arithmetic basic operations of addition , subtraction , multiplication and division can be carried out with binary numbers . In fact, the required algorithms are even simpler and can be implemented efficiently electronically using logic circuits. The introduction of binary numbers in computer technology therefore brought many advantages.

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0, carry 1

${\ displaystyle {{\ begin {matrix} & 1011_ {2} \\\ operatorname {+} & \ \ \ 11_ {2} \\\ end {matrix}} \ over {\ begin {matrix} & \ \ 1110_ { 2} \\\ end {matrix}}}}$
subtraction example

0 - 0 = 0
0 - 1 = 1, borrow 1
1 - 0 = 1
1 - 1 = 0

${\ displaystyle {\ begin {matrix} & 1011_ {2} \\ {- \} & \ \ 111_ {2} \\\ end {matrix}} \ over {\ begin {matrix} & \ \ \ \ \ 100_ { 2} \ end {matrix}}}$
multiplication example

0 0 = 0 0 1 = 0 1 0 = 0 1 1 = 1 ${\ displaystyle \ cdot}$
${\ displaystyle \ cdot}$
${\ displaystyle \ cdot}$
${\ displaystyle \ cdot}$

${\ displaystyle 1010_ {2} {\ cdot} 11_ {2} = 11110_ {2}}$
division example

0/0 = n.def.
0/1 = 0
1/0 = n.def.
1/1 = 1

${\ displaystyle 1010_ {2} {/} 10_ {2} = 101_ {2}}$

 A. B. M 1 M 2 E. 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1

Binary addition is a fundamental basic operation in the computer world. If you want to add two non-negative binary numbers and add them, you can do that as in the decimal system. You only have to note that in the result, no "two" is noted in the respective position, but a zero and a carryover to the next position. This is done in the same way as the decimal addition, if the addition of a digit results in a ten: ${\ displaystyle A}$${\ displaystyle B}$

The numbers are written on top of each other. Now all binary digits (= bits) from and are processed simultaneously from right to left and a result bit and a flag bit (also called carry ) are generated in each intermediate step . The bits are added up according to the table on the right. The bits of the numbers to be added can be found in columns A and B. The flag bit of the previous intermediate step is in the column . This results in a result bit (E) and a new flag bit ( ) (according to this table, which corresponds to a full adder ). All result bits, strung together from right to left, represent the result. If a flag bit is generated in the last intermediate step, the result is given an additional 1 on the left. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle M_ {1}}$${\ displaystyle M_ {2}}$

This is best seen with an example. Here the numbers A and B are added together. In each step a marker bit is noted for the next digit.

       A = 10011010 (154)
B = 00110110 (54)
Merker = 01111100
————————
Ergebnis = 11010000 (208)
‗‗‗‗‗‗‗‗


Written subtraction

The subtraction is analogous to the addition.

${\ displaystyle 0-0 = 0}$
${\ displaystyle 0-1 = 1}$, Borrow 1
${\ displaystyle 1-0 = 1}$
${\ displaystyle 1-1 = 0}$

Two numbers in the dual system can be subtracted from each other as shown in the following example:

${\ displaystyle {\ begin {matrix} & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ - &&& 1 & 0 & 1 & 1 & 1 \\ && {} _ {1} && {} _ {1} & {} _ {1} & {} _ {1} & \ end {matrix} } \ over {\ begin {matrix} = & 1 & 0 & 1 & 0 & 1 & 1 & 1 \ end {matrix}}}$

Here the subtraction 110−23 = 87 is carried out. The small ones in the third row show the carryover. The procedure is the same as that taught in the school for the decimal system. Case 0−1 looks a bit unusual. To clarify the example 2−9 in the decimal system: Imagine a tens place before the two, which results in the subtraction 12−9. The imaginary tens is then passed on as a carry over to the next digit. The same thing happens in the dual system: 0−1 becomes 10−1. As a result, a 1 can be written down; The one imagined in front of the 0 must then be written as a carry over to the next position and also deducted from it.

The procedure does not work (as in the decimal system) if the minuend (1st number) is smaller than the subtrahend (2nd number). If this is the case, a number is subtracted by adding the two's complement of this number. Subtracting a positive number gives the same result as adding the corresponding negative number with the same amount:

${\ displaystyle {\ begin {array} {crcccccccc | l | cr} && 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & {\ text {Minuend}} && 118_ {10} \\ - && 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & {\ text {Subtrahend}} & - & 0 & 1 & 1 & 1 & 1\ & 0 & 0 & 0_ & 1 & 1 & 1 & 0 {\ text {Minuend}} && 118_ {10} \\ + & (-) & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & {\ text {Subtrahend (two's complement)}} & + & (-) 153_ {10} \\ & {\ color {blue} {} _ {0}} & {} _ {1} & {} _ {1} &&& {} _ {1} & {} _ {1} &&& \\\ hline = && 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & {\ text {result (two's complement, negative) }} & = & - 35_ {10} \\\ hline \ hline && 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & {\ text {amount of the result}} && 35_ {10} \\\ end {array}}}$

If the carry (marked in blue) were 1, the two's complement of the result would no longer have to be formed, since the unsigned representation of the positive numbers in the two's complement is the same (see table there ). The carry is added to the leading ones (not shown) of the two's complement, which results in only leading zeros. The above calculation 110−23 = 87 serves as an example:

${\ displaystyle {\ begin {array} {crccccccc | l} && 1 & 1 & 0 & 1 & 1 & 1 & 0 & {\ text {Minuend}} \\ + & (-) & 1 & 1 & 0 & 1 & 0 & 0 & 1 & {\ text {Subtrahend (two's complement)}} \\ & {\ color {blue} { } _ {1}} & {} _ {1} && {} _ {1} &&&&& \\\ hline = && 1 & 0 & 1 & 0 & 1 & 1 & 1 & \ end {array}}}$

Written multiplication

The multiplication is carried out in the same way in the dual system as in the decimal system. Because only 0 and 1 appear as digits, the written multiplication is even easier. The following example, in which the numbers 1100 (12) and 1101 (13) are multiplied, shows the procedure.

First write the task in one line and draw a line below it to make things easier.

1100 · 1101
———————————


The first digit of the second factor is a one and therefore the first factor is right-justified under this one.

1100 · 1101
———————————
1100


For all other ones of the second factor, write the first factor right-justified underneath.

1100 · 1101
———————————
1100
1100
0000
1100


The numbers obtained in this way are then added together to form the result of the multiplication.

1100 · 1101
———————————
1100
+ 1100
+  0000
+   1100
———————————
10011100 (156)


A particularly simple case is the multiplication of a positive binary number by the number 10 (2). In this case, only a 0 has to be appended to the positive binary number:

${\ displaystyle 1101 \ cdot 10 = 11010}$
${\ displaystyle 11010 \ cdot 10 = 110100}$

etc.

Simple commands exist in digital technology for this arithmetic operation.

The Booth algorithm is used when multiplying two two 's complement dual numbers .

Written division

The following algorithms are used when dividing two binary numbers.

Using the example of the division of 1000010/11 (corresponds to 66: 3 in the decimal system)

   1000010 ÷ 11 = 010110 Rest 0 (= 22 im Dezimalsystem) somit mod
− 011
—————
00100
− 011
————
0011
− 011
—————
0


Applying the modulo function with the divisor 10 (2) to positive binary numbers always results in 1 if the last digit of the dividend is 1 and 0 if the last digit of the dividend is 0:

${\ displaystyle 1101 \ mod 10 = 1}$
${\ displaystyle 1100 \ mod 10 = 0}$

For this arithmetic operation, which corresponds to an AND operation with 1, there are simple commands in digital technology.

A particularly simple case is division with the remainder of a positive binary number by the number 10 (2). In this case only the last digit of the dividend has to be deleted. If the last digit of the dividend is 1, this remainder disappears.If with this procedure the number of divisions by 2 corresponds to the number of digits of the dividend, the end result is always 0:

${\ displaystyle 1101 \ div 10 = 110}$
${\ displaystyle 110 \ div 10 = 11}$
${\ displaystyle 11 \ div 10 = 1}$
${\ displaystyle 1 \ div 10 = 0}$

Simple commands exist in digital technology for this arithmetic operation.

Conversion of binary numbers into other place value systems

The small base has the disadvantage that numbers are relatively long and difficult to keep track of in relation to decimal numbers (see table below). This has led to the spread of the hexadecimal system, which the base 16 has. Since 16 is a power of 2, it is particularly easy to convert binary numbers into hexadecimal numbers. For this purpose, four digits of the binary number are replaced by a hexadecimal digit, which also reduces the length of the numbers displayed by a factor of four. The hexadecimal digits with the value 0–15 are usually represented by the number symbols 0–9 and the capital letters A – F (for the values ​​10–15). As a result, they are relatively easy to read, for example it is easy to determine that EDA5 (16) is larger than ED7A (16), whereas the corresponding binary numbers 1110110110100101 (2) and 1110110101111010 (2) cannot be overlooked so quickly.

 Dual system Decimal system Octal system Hexadecimal system 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 0 1 2 3 4th 5 6th 7th 8th 9 10 11 12 13 14th 15th 0 1 2 3 4th 5 6th 7th 10 11 12 13 14th 15th 16 17th 0 1 2 3 4th 5 6th 7th 8th 9 A. B. C. D. E. F.

From the dual system to the decimal system

In order to convert a binary number into the corresponding decimal number, all digits are multiplied by their place value (corresponding power of two) and then added.

Example:

${\ displaystyle 1010 _ {(2)} = 1 \ cdot 2 ^ {3} +0 \ cdot 2 ^ {2} +1 \ cdot 2 ^ {1} +0 \ cdot 2 ^ {0} = 1 \ cdot 2 ^ {3} +1 \ cdot 2 ^ {1} = 8 + 2 = 10 _ {(10)}}$

If the binary number ends with a 1, the decimal number is an odd number. If the last digit of the binary number is 0, the decimal number is even.

Example:

${\ displaystyle 101001 _ {(2)} = 1 \ cdot 2 ^ {0} +0 \ cdot 2 ^ {1} +0 \ cdot 2 ^ {2} +1 \ cdot 2 ^ {3} +0 \ cdot 2 ^ {4} +1 \ cdot 2 ^ {5} = 1 \ cdot 2 ^ {0} +1 \ cdot 2 ^ {3} +1 \ cdot 2 ^ {5} = 1 + 8 + 32 = 41 _ {( 10)}}$
${\ displaystyle 101000 _ {(2)} = 0 \ cdot 2 ^ {0} +0 \ cdot 2 ^ {1} +0 \ cdot 2 ^ {2} +1 \ cdot 2 ^ {3} +0 \ cdot 2 ^ {4} +1 \ cdot 2 ^ {5} = 1 \ cdot 2 ^ {3} +1 \ cdot 2 ^ {5} = 8 + 32 = 40 _ {(10)}}$

This procedure can also be written down in the form of a table. To do this, write down the individual digits of a binary number in columns, which are overwritten with the respective place value of the digit. In the following table, the priority is highlighted in orange. In each of the three lines of the white part there is a binary number:

 Status 32 16 8th 4th 2 1 Binary number 0 0 0 1 0 1 5 decimal number 1 0 0 0 1 1 35 0 0 1 0 1 0 10

You now add up all the place values ​​that are above the ones of the binary number and you get the corresponding decimal number with a green background. For example, to calculate the decimal value of the third binary number, the place values ​​8 and 2 are added. The result is 10.

This table method is also possible for place value systems for other bases; The peculiarity of the dual system is that the respective field entry ('0' or '1') does not have to be multiplied by the value of the position, but is used directly as a selection flag ('no' / 'yes') of this value for addition can be.

From the decimal system to the dual system

There are several ways of converting to the dual system. The division method (also called the modulo method ) is described below using example 41 (10) :

${\ displaystyle \ left. {\ begin {matrix} 41 &: 2 & = & 20 & \ mathrm {remainder} \ \ \ mathbf {1} \\ 20 &: 2 & = & 10 & \ mathrm {remainder} \ \ \ mathbf {0} \\ 10 &: 2 & = & 5 & \ mathrm {remainder} \ \ \ mathbf {0} \\ 5 &: 2 & = & 2 & \ mathrm {remainder} \ \ \ mathbf {1} \\ 2 &: 2 & = & 1 & \ mathrm {remainder} \ \ \ mathbf {0} \\ 1 &: 2 & = & 0 & \ mathrm {remainder} \ \ \ mathbf {1} \ end {matrix}} \ \ right \ uparrow}$

The corresponding binary number results from the notation of the calculated remainders from bottom to top: 101001 (2) .

Another method is the subtraction method. In this case, the greatest possible power of two is subtracted from the decimal number to be converted. If the next largest power of two is greater than the difference of the previous subtraction, the value of the next binary digit is 0. Otherwise, the next binary digit is 1 and the power of two is subtracted. To illustrate this method, let's use the number 41 as an example:

${\ displaystyle \ left. {\ begin {matrix} 41 & -2 ^ {5} & = & 9 & \ mathrm {value} \ \ \ mathbf {1} \\ 9 & -2 ^ {4} & <& 0 & \ mathrm {value } \ \ \ mathbf {0} \\ 9 & -2 ^ {3} & = & 1 & \ mathrm {value} \ \ \ mathbf {1} \\ 1 & -2 ^ {2} & <& 0 & \ mathrm {value} \ \ \ mathbf {0} \\ 1 & -2 ^ {1} & <& 0 & \ mathrm {weighting} \ \ \ mathbf {0} \\ 1 & -2 ^ {0} & = & 0 & \ mathrm {weighting} \ \ \ mathbf {1} \ end {matrix}} \ \ right \ downarrow}$

properties

Divisible by a power of 2

A number, represented by the base n, can be divided by the base n without a remainder (i-fold, i.e. by n i ) as often as the number has zeros at the end (i pieces). A binary number 100101000 2 can therefore be divided by 2 three times (= 2 3 ), since it ends with 3 zeros.

Divisible by 3

Let be a binary number where . We further define the set of ones in even places and the set of ones in odd places . Then applies to the number with respect to the divisibility by ( stands for the number): ${\ displaystyle n = b_ {k} \ dots b_ {0}}$${\ displaystyle b_ {i} \ in \ {0,1 \}}$${\ displaystyle G_ {1} (n) = \ {i \ mid \ exists j.b_ {2j} (n) = 1 \}}$${\ displaystyle U_ {1} (n) = \ {i \ mid \ exists j.b_ {2j + 1} (n) = 1 \}}$${\ displaystyle n}$${\ displaystyle 3}$${\ displaystyle \ #}$

${\ displaystyle | \ #G_ {1} (n) - \ # U_ {1} (n) | \ mod 3 = 0 \ implies n {\ text {is divisible by}} 3}$

In words, a binary number is divisible by 3 without a remainder if the difference in amount between the number of ones in the even positions and the number of ones in the odd positions is divisible by 3.

Example on the number : ${\ displaystyle n = 744628179621 _ {(10)}}$

The number has the following binary representation . It is and and actually${\ displaystyle n = 1010110101011111010011000101001010100101 _ {(2)}}$${\ displaystyle | \ #G_ {1} (n) - \ # U_ {1} (n) | = | 9-12 | = 3}$${\ displaystyle 3 \ mod 3 = 0}$${\ displaystyle 744628179621: 3 = 248209393207}$