Binary

We operate on the decimal system – every digit is between 0 and 9, and thus there are ten values, giving us the decimal 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 2power digit value (digit * 2power)
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.

Bitwise Operations

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

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 nots in a row cancel out, leaving us with just A and B! Much easier.

Practice Problems

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

  1. Convert 101101010111 to decimal.

  2. Convert 101101010111 to binary. (I’m evil, it’s true.)

  3. Simplify the following boolean expression: not((True or False) and (True or False))

  4. Simplify the following boolean expression: not(not(A XOR B) AND (B NAND A))

  5. Evaluate the following: (1101101 XOR 0101000) NOR 1001101

  6. Evaluate the following: (1101 OR 0011) AND (0011 XNOR 0010)