 # Review

## Review of number systems

All numbers represent a polynomial

... A5 ∙ B5 A4 ∙ B4 A3 ∙ B3 A2 ∙ B2 A1 ∙ B1 A0 ∙ B0 . A-1 ∙ B-1 A-2 ∙ B-2 ...

Where B represents the base of the number (i.e. 10 for decimal, 16 for hexadecimal, 8 for octal or 2 for binary,) and An represents some digit that is in the base.

## Decimal / Hexadecimal / Octal / Binary

Dec Hex Oct Bin
0 0 0 0000
1 1 1 0001
2 2 2 0010
3 3 3 0011
4 4 4 0100
5 5 5 0101
6 6 6 0110
7 7 7 0111
8 8 10 1000
9 9 11 1001
10 A 12 1010
11 B 13 1011
12 C 14 1100
13 D 15 1101
14 E 16 1110
15 F 17 1111
• Hexadecimal represents 4 binary bits. Usually prefixed with `0x` to indicate the number is hexadecimal, ex: 0xFC25
• Octal represents 3 binary bits. Usually prefixed with a leading 0 to indicate that the number is octal, ex: 0726
• Binary is sometimes prefixed with a leading `0b`.

### Hex/Octal to binary examples

``````         Hexadecimal                    Octal
┌───┬───┬───┬───┐             ┌───┬───┬───┐
0x │ F │ A │ 2 │ 5 │           0 │ 7 │ 2 │ 4 │
└───┴───┴───┴───┘             └───┴───┴───┘
│   │   │   │                 │   │   │
┌───┘ ┌─┘   └─┐ └───┐           ┌─┘   │   └─┐
│     │       │     │           │     │     │
┌──────┬──────┬──────┬──────┐    ┌─────┬─────┬─────┐
│ 1111 │ 1010 │ 0010 │ 0101 │    │ 111 │ 010 │ 100 │
└──────┴──────┴──────┴──────┘    └─────┴─────┴─────┘``````

## Review of Boolean Operations

All digital circuits in a computer are composed of these operations.

### AND / ∧

`A AND B` is true when both A and B are true, false otherwise. `∧` is the mathematical symbol for logical AND.

`A AND B AND C AND D ...` is true only when all operands are true, false otherwise

A B A AND B
0 0 0
0 1 0
1 0 0
1 1 1

Where 1 represents true and 0 represents false. In C Boolean logic any non-zero value represents true and only zero values represent false.

### OR / ∨

`A OR B` is true when either A or B are true, false otherwise. `∨` is the mathematical symbol for logical OR.

`A OR B OR C OR D ...` is true when any of the operands are true, false otherwise.

A B A OR B
0 0 0
0 1 1
1 0 1
1 1 1

### NOT / ¬

`NOT A` is the logical inverse of A. `¬` or a horizontal bar over an operand or expression is the mathematical operator for logical NOT.

A NOT A
0 1
1 0

### XOR (Exclusive OR) / ⊕

`A XOR B` is true if A and B are not the same, this is the same as the "not equal" operation. `⊕` is the mathematical symbol for XOR.

`A XOR B XOR C XOR D ...` is true if an odd number of operands are true, false otherwise

A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0

### NAND, NOR, XNOR

`NAND`, `NOR` and `XNOR` are the inverted result of the `AND`, `OR` or `XOR` operations.

A B A NAND B A NOR B A XNOR B
0 0 1 1 1
0 1 1 0 0
1 0 1 0 0
1 1 0 0 1

# C (& Python) Bitwise operations

## Binary operators

The bitwise operators operate similarly to the Boolean operations except they apply the operation to each individual bit of the two operands.

Operator Operation
`A | B` Bitwise OR of A and B
`A & B` Bitwise AND of A and B
`A ^ B` Bitwise XOR of A and B
`~ A` Binary NOT (i.e. binary inversion), inverts all bits of A
`A << N` Binary shift left A by N bits
`A >> N` Binary shift right A by N bits

### Example of Bitwise AND:

``````  A │ 0 0 1 1 1 0 0 1
& │ & & & & & & & &
B │ 1 0 1 1 0 1 0 1
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
A&B │ 0 0 1 1 0 0 0 1``````

## Binary shifting

When a integer is binary shifted to the left, each bit in the integer is moved one position upward towards the most significant bits. The first bit is replaced with a 0.

``````old:   0 1 1 0 1 1 0 1
<< 1    ╱ ╱ ╱ ╱ ╱ ╱ ╱
new:   1 1 0 1 1 0 1 0 ← 0``````

A shift to the left is equivalent to multiplying the value by 2 for each shift.

When shifting to the right, the behavior depends on whether the integer is signed or unsigned. If the integer is unsigned (i.e. can only represent a positive integer,) a shift right is similar to the left shift. The bits are shifted down and the upper bit is replaced with a zero.

``````old:     1 1 1 0 1 1 0 1
>> 1      ╲ ╲ ╲ ╲ ╲ ╲ ╲
new: 0 → 0 1 1 1 0 1 1 0``````

If the integer is signed, i.e. can represent both positive and negative values, the behavior is the bits are shifted down as normal, but the upper bit remains the same value it had before the shift.

``````old:   1 1 1 0 1 1 0 1      0 1 1 0 1 1 0 1
>> 1   │╲ ╲ ╲ ╲ ╲ ╲ ╲       │╲ ╲ ╲ ╲ ╲ ╲ ╲
new:   1 1 1 1 0 1 1 0      0 0 1 1 0 1 1 0``````

A shift to the right is equivalent to dividing the number by 2 for each shift. When the number is negative, it should remain negative after a division by 2, thus the reason for preserving the upper most bit (the sign bit) when the integer is signed.

# Basic bit operations

## Setting specific bits

To set a specific bit, you first create the bit to set by shifting a one to the desired location:

`mask = 1 << bitpos`

This creates a mask with the specific bit set and the rest of the mask are zero'ed bits. the mask is then OR'ed against the number you want to modify:

`num | mask`

The result will be num with the bit at bitpos set to a 1, as anything OR'ed against 1 will always result in a 1.

``````  ┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │ 1 │  num
└───┴───┴───┴───┴───┴───┴───┴───┘
OR
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │  (1<<4)
└───┴───┴───┴───┴───┴───┴───┴───┘
↓
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 0 │ 1 │ 1 │ 0 │ 1 │ 1 │  num | (1<<4)
└───┴───┴───┴───┴───┴───┴───┴───┘``````

It should be noted that `1 << N` is equivalent to 2N.

## Clearing specific bits

First create a mask where the bit to be zero'ed is zero and the rest of the mask is all ones. You can do this by inverting the mask after setting the bit to be cleared:

`mask = ~ (1 << bitpos)`

Then AND the mask against the number to be modified:

`num & mask`

The bits in num will pass through the mask unmodified where the mask is 1's and will always be 0 at bitpos.

``````  ┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │ 1 │  num
└───┴───┴───┴───┴───┴───┴───┴───┘
AND
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 1 │ 1 │ 1 │ 0 │ 1 │ 1 │ 1 │  ~(1<<3)
└───┴───┴───┴───┴───┴───┴───┴───┘
↓
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │ 1 │  num & ~(1<<3)
└───┴───┴───┴───┴───┴───┴───┴───┘``````

## Testing specific bits

To test if a specific bit is set, AND the number against a bitmask for the specific bits:

`num & (1<<bitpos)`

The result will be zero if the bit is unset and be equal to the bit value (1<<bitpos, i.e. non-zero) if the bit is set.

# Unsigned vs signed integers

When an integer is unsigned, the integer has a range of possible values from 0 to 2n-1 where `n` is the number of bits in the integer. When adding a number to an unsigned integer where the result is too large for the integer to hold, the upper bits of the result will be dropped and the result will be just the value of the lower bits.

### 8 bit example of unsigned integer overflow:

``````250 ⟶   1111 1010
+10 ⟶   0000 1010
260 ⟶ 1 0000 0100
⟶ X 0000 0100 ⟶ 4``````

When the integer is signed the upper bit is used to indicate that the number is negative, however the remaining bits are in two's compliment form. Subtracting from an unsigned integer where the result would be negative is still represented in two's compliment format.

## Adding and subtracting in Binary

Adding and subtracting works in the same manner as it does in Base-10, but with the limitation that you only have two digits to work with. When adding 1 and 1, the result is 0 with a carry of 1 (i.e. 10 which is 2 in binary.)

If adding bits A and B together, we can use a half-adder circuit to do so. The half adder is an incomplete adder in that it does not accept a carry input (i.e. the carry bit from a previous bit addition.) Later we will show a full adder which does accept the carry as input.

The half adder takes as its input, bits A and B and outputs a sum of the two bits and carry bit (when the sum of A and B is greater than 1.)

A B Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

From this truth table we can see that the sum is the XOR of A and B and the carry is the AND of A and B.

`````` A ──┬─┌─────┐
│ │ XOR ├── sum
B ┬─|─└─────┘
│ │
│ └─┌─────┐
│   │ AND ├── carry
└───└─────┘``````

A full adder would compute the output sum of one bit in an addition, along with the output carry (Cout) and would accept as its input the input bits A and B and also an input carry (Cin) from the previous bit being added.

A B Cin Sum Cout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Full adders would then be chained together to sum the bits of A and B. The carry out of each full adder is the carry input for the next full adder. This is called a ripple carry adder.

``````        A1  B1         A0  B0  0
──┐   │   │  ┌───┐   │   │  │
│   │   │  │   │   │   │  │
│  ┌┴───┴──┴┐  │  ┌┴───┴──┴┐
...  │  │   FA   │  │  │   FA   │
│  └──┬──┬──┘  │  └──┬──┬──┘
│     │  │     │     │  │
└─────┘  │     └─────┘  │
C1    S1       C0    S0``````

## Subtraction

When subtracting 1 from 0, you borrow from the next bit. If there is no next 1 bit to borrow from, you may borrow from an imaginary 1 bit beyond the end of the number being subtracted from.

``````      1 1 1 1 1 (borrows)
0 │   0 0 0 0
- 1 │ - 0 0 0 1
───    ───────
-1     1 1 1 1  (two's compliment for -1)``````

There are half and full subtractor circuits however we can use slightly a slightly modified ripple carry adder once we learn about two's compliment. The idea is that `A - B` is the same as `A + -B`. Converting one of the numbers to negative and then adding them will accomplish the same as subtracting.

## Two's compliment

Two's compliment

To represent a negative number in binary, invert the positive representation of it and add one:

``````-10 ⟶ 10 ⟶ 0000 1010
~10 ⟶ 1111 0101
+1 ⟶ 1111 0110  ⟶ -10``````

Alternatively you can subtract the number from 0 to arrive at the same result. Two's compliment form is used because it allows normal addition and subtraction of positive and negative values. A negative value need only be converted back to normal in order to print the value.

``````-10 ->   1111 0110
~-10  0000 1001
+1   0000 1010``````

An inverter can be constructed using XOR where one side of the XOR is always 1, the other input will be inverted on the output. If one side is always zero, then the output is the same as the other input.

``````   A 1    A 0
┌┴─┴┐  ┌┴─┴┐
│XOR│  │XOR│
└─┬─┘  └─┬─┘
¬A      A``````

When K in the ripple carry adder below is set to 0 it acts as a normal adder, however when set to 1 it will invert the bits of B and use the initial initial carry to do the addition of 1 to the result, turning B into proper twos compliment and then performing the addition of `A + -B`.

``````             B3             B2             B1             B0
──────────│─┬────────────│─┬────────────│─┬────────────│─┬────┬─ K
A3  ┌┴─┴┐      A2  ┌┴─┴┐      A1  ┌┴─┴┐      A0  ┌┴─┴┐   │
│  │XOR│       │  │XOR│       │  │XOR│       │  │XOR│   │
│  └─┬─┘       │  └─┬─┘       │  └─┬─┘       │  └─┬─┘   │
┌─┴────┴─┐     ┌─┴────┴─┐     ┌─┴────┴─┐     ┌─┴────┴─┐   │
... ────┤   FA   ├─────┤   FA   ├─────┤   FA   ├─────┤   FA   ├───┘
C3 └─────┬──┘  C2 └─────┬──┘  C1 └─────┬──┘  C0 └─────┬──┘
│              │              │              │
S4             S3             S1             S0``````

### Addition w/ two's compliment example

``````        1111 1100 <- carries
42 │ 0010 1010
+ -10 │ 1111 0110
─── │ ─────────
32 │ 0010 0000``````