## FoCS 04 - Calculating

### All calculating are based on bit

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

### 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.

1. If the operation is substraction, making `B` opposite, so that substraction becomes addition.
2. XOR operation to the signs of `A` and `B`, checking whether they have the same sign.
3. 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.
4. 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.

1. If A or B is zero, finishing the operation, and the result is the other number
2. If it’s a substraction, change the sign of B, so that substraction becomes addition
3. Reverse standardization: add 1 to the head of fraction parts of `A` and `B`
4. Adjusting the exponent, making the exponent of `A` and `B` be the same.
5. 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.
6. 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 ``````