Crypto-IT

Binary numbers are stored as sequences of zeros and ones. At present there are a couple of binary numeral systems in use. The most popular are:

• the Natural Binary System - in short NBS, which allows to store only nonnegative numbers,
• the Two's Complement System - in short 2C, which allows to store both positive and negative numbers.

A binary n-digit number stored in NBS, can have positive values ranging from 0 to 2ⁿ-1.

Using the natural binary system, one can present binary fixed point numbers. A certain part of the bits is used for storage of the fractional part of the number.

Binary addition of two numbers in NBS may be presented as simple columnar addition:

Binary subtraction of two numbers in NBS may be presented as simple columnar subtraction. One should subtract corresponding bits and if necessary borrow bits from columns on the left. The borrowed numbers have always values one greater than the base of the system is, so in this case 10 (or 2 in the decimal notation; for convenience the example below uses the latter number).

For example, after subtracting 6 from 19 in NBS, one will receive:

This is a correct result (13) in the decimal numeral system as well.

Binary multiplication of two numbers in NBS may be presented in the same way as multiplication of decimal numbers. For example, the result of multiplication of 22 and 5 (equal to 110) can be calculated in the following way (all the numbers are written in NSB):

Binary division of two numbers in NBS may be performed using shifting and subtraction.

One should write the two numbers under a horizontal line, the dividend over the divisor. The divisor should be moved left, until its most significant non-zero bit is located right under the most significant non-zero bit of the dividend.

Then the dividend should be compared to the divisor. If the dividend (the number written higher) is bigger than the divisor, one ought to subtract the divisor from the dividend and write 1 above the horizontal line in the last position. During the next comparison, one should use the result of the subtraction instead of the dividend.

If the divisor is bigger than the dividend, then no subtraction is performed. One ought to write 0 above the horizontal line in the last position, move the divisor (the number written lower) to the right by one position and repeat comparing.

If the divisor can't be moved to the right, than one should write 0 above the horizontal line in the last position. The current result of subtraction is the remainder of division.

For example, after dividing 11 by 3 one will receive the result 3 and the remainder 2:

After obtaining the remainder, it is possible to continue dividing and receive fractional digits (as during dividing of decimal numbers).

A binary n-digit number stored in C2, can have positive and negative values ​​ranging from -2^n-1 to 2^n-1-1.

The most-significant bit of a binary number in C2 is referred to as the sign bit and it determines if the number is positive or negative (the number is negative if the sign bit is equal to 1).

Numbers in C2 can be stored using various numbers of bits (numbers in the decimal system can also be stored using various numbers of digits, by adding zeros to the left side). In order to increase the number of bits of a binary number, one must add a new bit to the left side of binary sequence and set it to the same value as the sign bit has. This guarantees that the new number will have exactly the same value as the original one.

For example, a 4-digit binary number -7 stored in C2 (1001₂), can be extended to 5 bits by copying the sign bit (11001₂):
     1001₂ = -2³ + 2⁰ = -8 + 1 = -7
    11001₂ = -2⁴ + 2³ + 2⁰ = -16 + 8 + 1 = -7

Computing the inverse of a number in C2 is performed by negation of all the bits in the number (replacing zeros by ones, and ones by zeros) and then addition the result to 1.

For example, to calculate the value of number 11 in C2, knowing the binary representation of -11 in C2 (it is equal to 110101₂), one should in the first place negate all the bits:
    ~110101 = 001010,
and then add 1 to the result:

    2³ + 2¹ + 2⁰ = 8 + 2 + 1 = 11

Binary addition of two numbers in C2 may be presented as simple columnar addition, just like in NBS. For example, after adding 6 to -11 in C2, one will receive:

The result is equal to -5 in the decimal numeral system:
    -2⁵ + 2⁴ + 2³ + 2¹ + 2⁰ = -32 + 16 + 8 + 2 + 1 = -5

During performing the computations, one should remember that the result must fit within the same range to which the manipulated numbers are defined. Otherwise, the received value would have been incorrect.

Binary subtraction of two numbers in C2 may be presented as simple columnar subtraction, just like in NBS. The borrowed numbers have (like in NBS) values one greater than the base of the system is, so in this case 10 (or 2 in the decimal notation; to simplify the notation, the examples below use the latter number). For example, after subtracting 6 from -11 in C2, one will receive:

This is a correct result in the decimal numeral system as well:
    -2⁵ + 2³ + 2² + 2¹ + 2⁰ = -32 + 8 + 4 + 2 + 1 = -17

Similarly, to subtract 22 from -11 in C2 one should:

The result is equal to the decimal value:
    -2⁶ + 2⁴ + 2³ + 2² + 2¹ + 2⁰ = -64 + 16 + 8 + 4 + 2 + 1 = -33

Binary multiplication in C2 is slightly more complicated than in NBS. One of the efficient algorithms is called Booth's multiplication algorithm. In order to multiply two numbers: X of len_X bits and Y of len_Y bits, both stored in C2, one should perform the following Initialization steps:

1. If any of the given numbers (factors) is equal to the largest negative number which can be stored using as many bits as this factor has, then it should be expanded and a new bit should be added to its left side,
2. Calculate the inversion of X in C2 (-X),
3. Initialize the helper variable A of size of len_X+len_Y+1 bits: fill the most significant len_X bits of A with all the bits of X, and the rest len_Y+1 bits of A with zeros (A stands for addition, which is performed later during the algorithm),
4. Initialize the helper variable S of size of len_X+len_Y+1 bits: fill the most significant len_X bits of S with all the bits of -X, and the rest len_Y+1 bits of S with zeros (S stands for shifting, which is performed later during the algorithm),
5. Initialize the helper variable P of size of len_X+len_Y+1 bits: fill the most significant len_X bits of P with zeros, then the next len_Y bits of P with all the bits of Y, and the last (the least significant) bit of P set to 0 (P stands for product, the result of multiplication).

After initialization of variables, one should repeat the two steps below len_Y times:

1. If the two last bits of P are equal to 01, then one should compute P+A (ignoring any overflow) and assign the result to P. Otherwise, if the two last bits of P are equal to 10, then one should compute P+S (ignoring any overflow) and assign the result to P. Otherwise, if they are equal to either 00 or 11, then P should remain unchanged.
2. All the bits of the current number P should be arithmetically shifted right by one position (abandoning the least significant bit and leaving unchanged the value of the most significant bit) and the result ought to be assigned to P.

Finally, after completing the steps above, one should remove the least significant bit from the received number P. The result (the new value of P) is the product of multiplication of the two numbers X and Y.

Let's consider the multiplication of -8 and 3:

    X = -8 = 1000₂
    Y = 3 = 011₂

In the first step, the number X should be extended:
    X = 11000

Then, it is necessary to calculate the value of -X:
    -X = ~11000 + 01 = 00111 + 01 = 01000

Calculating the values of helper variables A, S and P:
    A = 1 1000 0000
    S = 0 1000 0000
    P = 0 0000 0110

Then the next two steps of the algorithm should be repeated three times (because the number Y is 3-bit long):
 Iteration 1:
    P = P + S = 0 1000 0110
    P >> 1 = 0 0100 0011
 Iteration 2:
    P >> 1 = 0 0010 0001
 Iteration 3:
    P = P + A = 1 1010 0001
    P >> 1 = 1 1101 0000

In the end, it is necessary to remove the least significant bit of P:
    P = 1110 1000

The result is equal to:
    -2⁷ + 2⁶ + 2⁵ + 2³ = -128 + 64 + 32 + 8 = -24

This is a correct result of multiplication of -8 and 3.