Penetration testing course: 0x02.1 Fundamentals of binary arithmetic

Any information processed by a computer is stored in binary format so it is fundamental that anyone is familiar with this numeral system.

DECIMAL SYSTEM

decimal system - ten fingers

                  decimal system – ten fingers

When we count we normally use the decimal system (base 10). Ten is the number which is the count of fingers and thumbs on both hands (or toes on the feet).

Positional decimal systems include a zero and use symbols (called digits) for the ten values (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) to represent any number, no matter how large or how small. These digits are often used with a decimal separator which indicates the start of a fractional part, and with a symbol such as the plus sign + (for positive) or minus sign − (for negative) adjacent to the numeral to indicate whether it is greater or less than zero, respectively.

Positional notation uses positions for each power of ten: units, tens, hundreds, thousands, etc. The position of each digit within a number denotes the multiplier (power of ten) multiplied with that digit—each position has a value ten times that of the position to its right.

We all know about arithmetic using the decimal numeral system so I won’t talk about this.

BINARY SYSTEM

binary

                                        binary

The binary system represents numeral values using 2 different symbols (0, 1). The base-2 system is a positional notation with a radix of 2. Because of its straightforward implementation in digital electronic circuitry using logic gates, the binary system is used internally by almost all modern computers and computer-based devices. Each digit is referred to as a bit.

BINARY COUNTING

Counting begins with the incremental substitution of the least significant digit (rightmost digit). When the available symbols for this position are exhausted, the least significant digit is reset to 0, and the next digit of higher significance (one position to the left) is incremented (overflow), and incremental substitution of the low-order digit resumes. This method of reset and overflow is repeated for each digit of significance.

Binary

                           Binary

BINARY TO DECIMAL CONVERSION

In the binary system, each digit represents an increasing power of 2, with the rightmost digit representing 20, the next representing 21, then 22, and so on. The equivalent decimal representation of a binary number is sum of the powers of 2 which each digit represents.

For example, the binary number 100101 is converted to decimal form as follows:

1001012 = [ ( 1 ) × 25 ] + [ ( 0 ) × 24 ] + [ ( 0 ) × 23 ] + [ ( 1 ) × 22 ] + [ ( 0 ) × 21 ] + [ ( 1 ) × 20 ] 1001012 = [ 1 × 32 ] + [ 0 × 16 ] + [ 0 × 8 ] + [ 1 × 4 ] + [ 0 × 2 ] + [ 1 × 1 ] 1001012 = 3710

DECIMAL TO BINARY CONVERSION

Take the decimal number and divide it by 2, then take note of the reminder (0 or 1). Repeat the operation dividing the last result by 2 and keep note of the reminder until the result is 0.

For example, the decimal number 13 is converted to binary form as follows:

13 / 2 = 6  reminder: 1

6 / 2 = 3  reminder: 0

3 / 2 = 1  reminder: 1

1 / 2 = 0  reminder: 1

1310 = 11012

BINARY ARITHMETIC

ADDITION

The simplest arithmetic operation in binary is addition. Adding two single-digit binary numbers is relatively simple, using a form of carrying:

0 + 0 → 0
0 + 1 → 1
1 + 0 → 1
1 + 1 → 0, carry 1 (since 1 + 1 = 2 = 0 + (1 × 21) )
Adding two “1” digits produces a digit “0”, while 1 will have to be added to the next column. This is similar to what happens in decimal when certain single-digit numbers are added together; if the result equals or exceeds the value of the radix (10), the digit to the left is incremented:

5 + 5 → 0, carry 1 (since 5 + 5 = 10 = 0 + (1 × 101) )
7 + 9 → 6, carry 1 (since 7 + 9 = 16 = 6 + (1 × 101) )
This is known as carrying. When the result of an addition exceeds the value of a digit, the procedure is to “carry” the excess amount divided by the radix (that is, 10/10) to the left, adding it to the next positional value. This is correct since the next position has a weight that is higher by a factor equal to the radix. Carrying works the same way in binary:

1 1 1 1 1 (carried digits)
0 1 1 0 1
+  1 0 1 1 1
————-
= 1 0 0 1 0 0 = 36

In this example, two numerals are being added together: 011012 (1310) and 101112 (2310). The top row shows the carry bits used. Starting in the rightmost column, 1 + 1 = 102. The 1 is carried to the left, and the 0 is written at the bottom of the rightmost column. The second column from the right is added: 1 + 0 + 1 = 102 again; the 1 is carried, and 0 is written at the bottom. The third column: 1 + 1 + 1 = 112. This time, a 1 is carried, and a 1 is written in the bottom row. Proceeding like this gives the final answer 1001002 (36 decimal).

When computers must add two numbers, the rule that: x xor y = (x + y) mod 2 for any two bits x and y allows for very fast calculation, as well.

Long carry method
A simplification for many binary addition problems is the Long Carry Method or Brookhouse Method of Binary Addition. This method is generally useful in any binary addition where one of the numbers contains a long “string” of ones. It is based on the simple premise that under the binary system, when given a “string” of digits composed entirely of n ones (where: n is any integer length), adding 1 will result in the number 1 followed by a string of n zeros. That concept follows, logically, just as in the decimal system, where adding 1 to a string of n 9s will result in the number 1 followed by a string of n 0s:

Binary                                       Decimal
1 1 1 1 1          likewise              9 9 9 9 9
+        1                                     +             1
————–                                —————-
1 0 0 0 0                              0 1 0 0 0 0 0

Such long strings are quite common in the binary system. From that one finds that large binary numbers can be added using two simple steps, without excessive carry operations.

SUBSTRACTION

Subtraction works in much the same way:

0 − 0 → 0
0 − 1 → 1, borrow 1
1 − 0 → 1
1 − 1 → 0
Subtracting a “1” digit from a “0” digit produces the digit “1”, while 1 will have to be subtracted from the next column. This is known as borrowing. The principle is the same as for carrying. When the result of a subtraction is less than 0, the least possible value of a digit, the procedure is to “borrow” the deficit divided by the radix (that is, 10/10) from the left, subtracting it from the next positional value.

*      * * * (starred columns are borrowed from)
1 1 0 1 1 1 0
−     1 0 1 1 1
—————-
= 1 0 1 0 1 1 1

* (starred columns are borrowed from)
1 0 1 1 1 1 1
– 1 0 1 0 1 1
—————-
= 0 1 1 0 1 0 0

Subtracting a positive number is equivalent to adding a negative number of equal absolute value. Computers use signed number representations to handle negative numbers—most commonly the two’s complement notation. Such representations eliminate the need for a separate “subtract” operation. Using two’s complement notation subtraction can be summarized by the following formula:

A − B = A + not B + 1

Multiplication

Multiplication in binary is similar to its decimal counterpart. Two numbers A and B can be multiplied by partial products: for each digit in B, the product of that digit in A is calculated and written on a new line, shifted leftward so that its rightmost digit lines up with the digit in B that was used. The sum of all these partial products gives the final result.

Since there are only two digits in binary, there are only two possible outcomes of each partial multiplication:

If the digit in B is 0, the partial product is also 0
If the digit in B is 1, the partial product is equal to A
For example, the binary numbers 1011 and 1010 are multiplied as follows:

multiplication

                             multiplication

Binary numbers can also be multiplied with bits after a binary point:

multiplication

                               multiplication

Multiplication table

multiplication table

        multiplication table

Division

Binary division is again similar to its decimal counterpart:

Here, the divisor is 1012, or 5 decimal, while the dividend is 110112, or 27 decimal. The procedure is the same as that of decimal long division; here, the divisor 1012 goes into the first three digits 1102 of the dividend one time, so a “1” is written on the top line. This result is multiplied by the divisor, and subtracted from the first three digits of the dividend; the next digit (a “1”) is included to obtain a new three-digit sequence:

division

                                   division

The procedure is then repeated with the new sequence, continuing until the digits in the dividend have been exhausted:

division

                          division

Thus, the quotient of 110112 divided by 1012 is 1012, as shown on the top line, while the remainder, shown on the bottom line, is 102. In decimal, 27 divided by 5 is 5, with a remainder of 2.


 

Please note: a CPU only executes additions, it doesn’t perform substractions, multiplications or divisions.

Addition:  a + b (nothing strange here).

Substraction: a + (-b).

Multiplication: a * b (if a=2 and b= 4, then it is equal to “2 + 2 + 2+ 2” or “4 + 4”. I used the decimal system for simplicity but keep in mind operations are performed in binary).

Division: a / b (if a = 4 and b = 2, then it is equal to 4 + (-2) = 2. The reminder is 0 so the operation is complete.) This was the easiest example anyway in order to understand consider that the “long division” alghorithm shifts gradually from the left to the right end of the dividend, subtracting the largest possible multiple of the divisor at each stage; the multiples become the digits of the quotient and the final difference is the remainder.

Also the bitwise operations that will be convered in the next paragraph are executed by the CPU as a particular form of addition.


 

BITWISE OPERATIONS

Now that we learnt how to represent binary numbers we can see some low level operations.

Computers can manipulate bits directly using bitwise operations. The kinds of operations are very used in network addressing and assembly programming.

NOT operator – bitwise negation:

it takes the value given and switches all the binary 1s to 0s and 0s to 1s

Example: NOT 1101 = 0010


AND operator – logical conjuction

if both bits in the same position are 1 the operation returns 1, otherwise 0

Example: 1001 AND 1100 = 1000


OR operator – logical (inclusive) disjunction

if at least one of the two bits is 1, the operation returns 1, otherwerwise it returns 0 if both bits are equal to 0

Example: 1001 OR 1100 = 1101


XOR operator – logical (exclusive) disjunction

if one and only one of the two bits is equal to 1, the operation returns 1, otherwise it returns 0 if at least one bit is 0

Example: 1001 XOR 1100 = 0101

This is the end for today’s lesson. Please come back for the next article that will deal with the hexadecimal system, another important numeral system used in computer science.

p.s. I wanted to start from the basics in order to make the course beneficial for everyone. If this seems too easy for you, you can skip to the next lessons. Keep in mind though that knowledge about the numeral systems is important for Low Level Programming (mainly Assembly and C/C++), Reverse Engineering of Software, Malware Development/Analysis, Exploit Development/Shellcoding so you may want to review this part when you reach that point. Cheers!

Did you enjoy this article?
Signup today and receive free updates straight in your inbox. We will never share or sell your email address.

Author: Fabio Baroni   Date: 2015-12-20 18:56:39

Related posts:

Comments 1

  1. Pingback: Kevin

Leave a Reply

Your email address will not be published. Required fields are marked *