FoCS 04 - Calculating

The story of cover: the enigma machine made by Alan Turing

# Logical operation

# Boolean type

Boolean is used for describing authenticity of things in computer, which only includes two status: True and False, so it’s really easy to present it in computer.

We can only use one bit to present boolean value:

Boolean	Bit value	Meaning
True	1	The condition is meeted or the thing is true
False	0	The condition is unmeeted or the thing is false

Boolean is a data type in programming rather than a data type in daily use(they are all called data type, but different meaning). That’s why I put it here rather than last post.

All logical operation is operation works on boolean value(single bit value).

# NOT operation

NOT operation only needs one boolean involving.
It means the opposite thing: not true means false, and not false means true, which is easy to understand.

Before NOT	After NOT
1 (true)	0 (false)
0 (false)	1 (true)

# AND operation

AND operation needs two boolean involving.
Only you can get True when two things are True at same time.

Boolean 1	Boolean 2	Result
0 (false)	0 (false)	0 (false)
1 (true)	0 (false)	0 (false)
0 (false)	1 (true)	0 (false)
1 (true)	1 (true)	1 (true)

# OR operation

OR operation needs two boolean involving as well.
Only you can get False when two things are False at same time.

Boolean 1	Boolean 2	Result
0 (false)	0 (false)	0 (false)
1 (true)	0 (false)	1 (true)
0 (false)	1 (true)	1 (true)
1 (true)	1 (true)	1 (true)

# XOR operation

XOR operation needs two boolean involving as well.

When two things are the same gets False
When two things are different gets True

Boolean 1	Boolean 2	Result
0 (false)	0 (false)	0 (false)
1 (true)	0 (false)	1 (true)
0 (false)	1 (true)	1 (true)
1 (true)	1 (true)	0 (false)

# Shift operation

# Logical shift operation

Shifting the whole bit sequence to left or right

# Non-loop logical shift

In this case, after the shift, the overflow parts will be ignored, and the new space will be filled by zero.

Shifting a 8-length bit sequence for 1 bit

1
2
3
4
5
6
7
8


index       12345678         12345678
 data       11001010   -->   011001010
                             ^       ^
                             |       | 
                             |       ingored
                             new added   

the result is 01100101

# Loop logical shift

In this case, you can imagine the whole bit sequence is a circle. After the shift, nothing will be lost but the order.

Shifting a 8-length bit sequence for 1 bit

1
2
3
4
5
6


index       12345678         12345678
 data       11001010   -->   01100101
                             ^      ^
                             |      | 
                             |      the second last number before shifitng
                             the last number before shifting

# Arithmetic shift operation

Shifting the bit sequence including sign to left or right. In other words, the bit sequence needs shift is a number with sign. So it can only be used on bit sequences presenting numbers.

# Shift to Left

In this operation, the process of shift to left and shift to right have a few of differences.

The content after shift will cover the sign, and new spaces will be filled by zero. If the sign has changed in the shift, which means the overflow happens.

1
2
3
4
5
6


Example 1: no overflow happens
Sign    Data        <-----      Sign    Data    
0       0011010     2 bits      0       1101000
                                             ^^
                                             ||
                                             they are new added

1
2
3
4
5
6
7
8


Example 2: overflow happens
Sign    Data        <-----      Sign    Data
0       1010110     1 bit       1       0101100
                                ^             ^
                                |             |
                                |             new zero added  
                                sign changed, overflow happens
                                you can't trust any shift result based on that

# Shift to right

All data will move to right, excepting the sign. The empty space will be filled by sign and the surpassed tail will be ignored.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Example 1: positive number shifting
Sign    Data        ----->      Sign    Data
0       1010110     1 bit       0       0101011       
                                        ^
                                        |
                                        the sign is 0, so it's filled by 0
1       1010110     1 bit       1       1101011
                                        ^
                                        |
                                        the sign is 1, so it's filled by 1

# Arithmetic operation

At this place, we only talk about addition and subtraction.

# Between two’s complements

It’s the most simple situation. You can just calculate it like decimal numbers, the only difference is you need to ignore the last column carry if exists.

For substraction, you can use the two’s complement to make the it becomes addition.

1
2
3
4
5
6


Example 1: simple addition
      1         carry bit
    00010001    num1
+   00010110    num2
--------------------
    00100111    result

1
2
3
4
5
6
7


Example 2: simple addition with overflow
    1111111     carry bit
    01111111    num1
+   00000011    num2
--------------------
    10000010    result
Because of the overflow, the sign has changed, and the result is wrong

1
2
3
4
5
6
7
8
9


Example 3: ignore the last column carry
   ignore it
   |
   V
   111111       carry bit
    11011101    num1
+   11101100    num2
--------------------
    11001001    result

# Between absolute values with sign

In this case, we use sign and absolute value to present a number rather than two’s complement.
Here are the steps:
For easier illustration, A means the first number, and B means the second number.

If the operation is substraction, making B opposite, so that substraction becomes addition.
XOR operation to the signs of A and B, checking whether they have the same sign.
If the result is 0 means they have the same sign, we can add the absolute value directly and the sign won’t change after calculation. If any overflow happens, the result is wrong.
Otherwise, the sign is different, calculating the two’s complement of the absolute value of B, and adding it to the absolute value of A, and the sign is the same as which number has bigger absolute value.
- If A has bigger absolute value, the sign will be the same as A and we can ignore the overflow
- If B has bigger absolute value, the sign will be the same as B and getting the two’s complement of the result

1
2
3
4
5
6
7


Example 1: 17+22
    Sign    ABS
                        carry
    0       0010001     A 
+   0       0010110     B
---------------------------
    0       0100111     result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Example 2: 17+(-22)
    Sign    ABS
                        carry
    0       0010001     A 
+   1       0010110     B
---------------------------
    0       0010001     A 
+   1       1101010     two's complement of B
---------------------------
(B has bigger absolute value, so the sign is the same as B)
    1       1111011     two's complement of the result
    1       0000101     the result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


Example 3: (-81)-(-22)
    Sign    ABS
                        carry
    1       1010001     A 
-   1       0010110     B
---------------------------
    1       1010001     A 
+   0       0010110     B
---------------------------
           1            carry 
    1       1010001     A
+   0       1101010     two's complement of abs of B
---------------------------
    1      10111011     temp result
(the overflow should be ignored)
    1       0111011     the result      

# Between real number

For easier illustration, A means the first number, and B means the second number.

If A or B is zero, finishing the operation, and the result is the other number
If it’s a substraction, change the sign of B, so that substraction becomes addition
Reverse standardization: add 1 to the head of fraction parts of A and B
Adjusting the exponent, making the exponent of A and B be the same.
It includes 2 situations:
- the sign of A and B are the same: keep the sign and add the fraction
- the sign of A and B are different: sign is which has bigger fraction, and bigger fraction minus smaller one.
Standardization and get the result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


Example 1: 5.75 + 161.875
S       E           M
0       10000001    0111            A
0       10000110    0100001111      B

Unstandardization:
S       E           M
0       10000010    10111           A
0       10000111    10100001111     B

Adjust the exponent of A and B:
S       E           M
0       10000111    0000010111      A
0       10000111    10100001111     B

Adding the fraction parts of A and B:
    S       E           M
    0       10000111    0000010111      A
+   0       10000111    10100001111     B
--------------------------------------
0       10000111    10100111101

Standardization:
S       E           M
0       10000110    0100111101

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


Example 2: 5.75 + (-7.0234375)
S       E           M
0       10000001    0111            A
1       10000001    110000011       B

Unstandardization:
S       E           M
0       10000010    10111           A
1       10000010    1110000011      B

The exponents are the same
B has bigger fraction when the exponents are the same
1. Sign is the same as B
2. Fraction of B minus fraction of A
    S       E           M
    1       10000010    1110000011      B
-   0       10000010    10111           A
--------------------------------------
    1       10000010    0010100011
    
Standardization:
S       E           M
1       01111111    0100011