Bits & Logic

Continuing our discussion on bits, let's talk more about how we can mess with the states system we described earlier. Before that, lets clarify some notation:

Logic

You've definitely heard the term often, but how deeply have you understood the fundamentals of it? You can find an elongated definition on Wikipedia for Mathematical Logic, but lets define it simply as conclusions and reasoning of truths.

Notation

• x = y means y is assigned to x, or, x is now what y is.
• x == y is a statement about equivalence "x is the same as y".

The second thing is a question of whether x is the same as y or not. As an example, say x = 7; y = 3. If we now say:

x == y

The answer to the question would be False. We could also write it as:

(x == y) -> False

This could also be said as x == y implies False.

To make logic easy to write in concise ways, we define abstract things as variables. Something like:

• S: "Today it's sunny"
• R: "Toady it's rainy"

Now just having truths assigned to variables would make logic very useless, so they only become useful when we apply operations to them. These operations are called logic operations. There are 4 fundamental logic operators:

• AND
• OR
• NOT
• XOR

Let't talk about each one.

AND

AND works logically like how you use it in english. Its useful for understanding the truth of two things. As an example:

S: "Today it's sunny"
R: "Today it's rainy"

S = True
R = False

(S AND R) -> False

Let's decode the above. First, we defined S and R as shorthand notation for an abstract thing like the state of the day (being rainy or sunny). Next we described the truth of the states we defined. "Today it's sunny" is True; then we said "Today it's rainy" is False. Lastly, we evaluated the truth value of:

(S AND R)

or the statement:

Today it is sunny AND it is rainy, which is False.

It's False because we had earlier said that it was not rainy today. In this way, you can treat AND like a function that takes two arguments AND(x, y). The input is two truth variables (which could be true or false), and the output is True or False. Let's shorten the state True to T and False to F. With all your knowledge we can easily define all the possible outputs of AND, known as a truth table.

As you can see, the output is only ever True if both X and Y are true. After all of this, it will be much easier to define the other operators.

OR

OR is very similar to AND. It takes two truth values and outputs True if just one of the two are True. Here is the truth table:

NOT

NOT is special because it only takes a single truth value. All NOT does is reverse the truth of its argument. Here is the truth value:

Its useful now though to say that you can compound logical operators:

In addition to that, NOT also has a special reversing mechanic on AND and OR. For instance:

(NOT(X OR Y)) == (NOT(X) AND NOT(Y))

You can test that above by making your own truth table. Notice how you can distribute the NOT to each variable and the operator, which flipped it to AND. The same is true in the reverse.

XOR

XOR takes two truth values like the others, but is less used in normal english. Its short for Exclusive, which means the output is only true when the inputs differ:

Notice how it is only True when things going in are different from each other? Its an interesting mechanic and will be used more later.

Now that we have a high level understand of logic, we can now relate it

Bit Logic

Logic with bits work exactly the same as logic in general. True is 1; False is 0.

Notation

Here is our new notation that is generally for bit logic:

AND: &
OR: |
NOT: !
XOR: ^

All of them still work the same, but now if I want to say x AND y I would actually say x & y.

Multi-Bit Logic Operations

Operations on variables with bits work even on the byte level:

x = 11110101    
y = 00101101

(x & y) == 00100101

How did the above work? If you look closely, each logic operation was applied on each individual bit it lined up with.

Now, recall that bits can also be represented as hex! This means we can do logic operations on things that look like numbers (but remember they are bits under the hood):

x = 0x13 (00010011) 
y = 0x32 (00110010)

(x & y) == 0x33 (00110011)

This entire time we have been using bytes, but to keep with the earlier theme, why don't we assume that we can represent things in 64bits. For conciseness, we don't write leading 0's in a hex number:

x = 0xcafe (64 bits)
y = 0xbabe (64 bits)

(x ^ y) == 0x0000000000007040

The zeros are shown in the result just to clarify once again that we are in 64bits, but all the operations we have done before still work. Remember you can always compound logic statements on other logic statements (and store them in another variable if you).

Logic Gates

All these bit operations are actually mechanics of real-world hardware that things run on. Since electricity is like a 1 or a 0, it makes sense that these logic gates are what we first implemented in hardware.

Circuit Engineers annotate these gates like shown here. Generally speaking, all things on computers first start with these fundamental logic gates that are implemented in hardware.

Now that we understand how to truly utilize the power of bits and logic, we can move on to understand a computer at its lowest level.