Boolean Algebra

Boolean algebra is the original theory that deals with only true and false. This area of math gave us AND, OR, XOR, NOT, and more for boolean inputs.

It's the basis of the bitwise and binary-arithmetic fields. In the end, computers use boolean operators to do binary arithmetic.

Boolean to Binary Encoding

This is a key mental model. Binary and boolean aren't the same. Binary is just used to represent boolean values.

Standard Boolean Operators

Operator	Symbol	Description	Input causing output = True	Input causing output = False
NOT	¬, ~	Flips the value	Input = False	Input = True
AND	∧, ·	True only if both are true	Both True	Any False
OR	∨, +	True if at least one is true	Any True	Both False
XOR	⊕, ⊻	True if inputs are different	Inputs differ	Inputs same
NAND	↑, ⊼	Opposite of AND	Any False	Both True
NOR	↓, ⊽	Opposite of OR	Both False	Any True
XNOR	⊙, ≡	True if inputs are the same	Inputs same	Inputs differ

different from bitwise operators

Bitwise operators aren't part of boolean algebra. We often call everything bitwise, but that's wrong.

Bit shifts and rotates are the bitwise operators.

Arithmetic Negation

Arithmetic negation is the negative form of a positive number. The best mental model is the modular operation. It uses a circular counter. For positive numbers, you move clockwise from zero. For negative numbers, you move the other way from zero.

How to generate -x from x?

Since $x + (-x) = 0$, negating gives the value that, when added to the original, brings the pointer on the ring back to zero. So $-x$ is always ($\sim{x}) + 1$.

The $+1$ makes the counter reach zero.

Remember this key model. At the CPU register level, numbers sit on a circular ring. It starts at 0 and goes up to $2^{n}$, based on the variable size.

-x isn't geometrical opposite of x

When you view the number range as a circle, x isn't geometrically opposite to -x.

different negations possible

• $!$ Boolean NOT. Flips true to false and vice versa.
• $-$ Arithmetic negation - Subtracts a number from zero.
• $\sim$ Bitwise NOT - Flips every individual bit from 0 to 1 and 1 to 0.