We operate on the decimal system – every digit is between `0`

and `9`

, and thus there are *ten* values, giving us the *dec*imal system.

Binary is just the same way, only there are only two values: `0`

and `1`

.

You can represent numbers in precisely the same way in both systems.

Let’s examine the number `500`

. How do we know what the value of `500`

is? The right most digit, `0`

, is the *ones* place. But what does *ones* really mean? It means whatever value is there, multiply it by `10^0`

(ten to the power zero). Similarly, the *tens* place is `10^1`

, the hundreds place is `10^2`

, etc.

We take the values and add them up. So we get `5 * 10^2 + 0 * 10^1 + 0 ^ 10^0`

, which adds up to be `500`

.

Let’s look at a binary number now: `11011`

. The process works the same way.

Let’s make a table.

power | 2^{power} |
digit | value (digit * 2^{power}) |
---|---|---|---|

0 | 1 | 1 | 1 |

1 | 2 | 1 | 2 |

2 | 4 | 0 | 0 |

3 | 8 | 1 | 8 |

4 | 16 | 1 | 16 |

So now we simply add up the `value`

column: `1 + 2 + 0 + 8 + 16`

, giving us our result `27`

!

This is the same process for every single number in binary.

There are several bitwise operations you need to learn, and in fact you already know them with booleans! One way to think about this is that `1`

is equivalent to `True`

and `0`

is `False`

.

The way we define these is using **truth tables**. Truth tables have one column per input and one column for the output; as you can guess, every value either has to be True or False (or 0 or 1).

The most simple is `!`

, which is the bitwise equivalent of `not`

.

x | ! x |
---|---|

0 | 1 |

1 | 0 |

`&`

is the bitwise equivalent of `and`

.

x | y | x & y |
---|---|---|

1 | 1 | 1 |

1 | 0 | 0 |

0 | 1 | 0 |

0 | 0 | 0 |

This is the exact same table for `and`

if you replace the `1`

with `True`

and `0`

with `False`

.

`|`

is the bitwise version of `or`

.

x | y | x | y |
---|---|---|

1 | 1 | 1 |

1 | 0 | 1 |

0 | 1 | 1 |

0 | 0 | 0 |

Nothing new so far. Now we get to the new bitwise operations that we didn’t see for the booleans.

`xor`

is *exclusive* or. Unlike the standard or function, `xor`

is only true when just *one* of the inputs is true.

x | y | x ^ y |
---|---|---|

1 | 1 | 0 |

1 | 0 | 1 |

0 | 1 | 1 |

0 | 0 | 0 |

`nor`

is simply a `not`

in front of an `|`

.

`nand`

is a `!`

in front of an `&`

.

`xnor`

is a `!`

in front of an `^`

.

Those are pretty much all of the major gates! As an exercise, see if you can write the truth tables for the last three gates that I showed you.

Here’s a question to see if you were paying attention: How many rows does a truth table have? (Assume the number of inputs is `n`

.)

Boolean algebra uses these exact same gates to reduce complicated problems into simpler ones. At the heart of this is **De Morgan’s Law**. De Morgan’s law is quite simple: when you’re adding a *not* in front of a large boolean expression, flip the ors into ands (and vice versa) and add a not in front of each variable.

Let’s take an example.

`not((not A) or (not B))`

Hmm. Seems needlessly messy. Surely there must be a way to reduce this. Why not De Morgan’s law? The first part says to flip ors and ands. That leaves us with this.

`(not A) and (not B)`

Then we add a not to each of the elements, giving us the following:

`(not not A) and (not not B)`

But of course two `not`

s in a row cancel out, leaving us with just `A and B`

! Much easier.

Let’s get used to these new fangled notations and functions.

Convert

`101101010111`

to decimal.Convert

`101101010111`

to binary. (I’m evil, it’s true.)Simplify the following boolean expression:

`not((True or False) and (True or False))`

Simplify the following boolean expression:

`not(not(A XOR B) AND (B NAND A))`

Evaluate the following:

`(1101101 XOR 0101000) NOR 1001101`

Evaluate the following:

`(1101 OR 0011) AND (0011 XNOR 0010)`