## Intro

Relating to a numbering system with a base of 2. The largest digit usable is one, just as in a decimal system where the largest digit usable is 9. Each digit in a binary number is 2 to the power of the digit's position, with the first position being the power of zero. Machine languages are written in binary.

The following may or may not be helpful in explaining a binary numbering system:

• Binary counts as follows: 0, 1, 10, 11, 100, 101, 110,.... For comparison, decimal counts as follows: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,....
• Binary numbers often occur in octets (sets of eight). The positions of the octet may be numbered (from left to right) 7, 6, 5, 4, 3, 2, 1, and 0. The maximum in each position is 2 to that power. The value of each digit in each position would be 2^7=128, 2^6=64, 2^5=32, 2^4=16, 2^3=8, 2^2=4, 2^1=2, and 2^0=1. For comparison, for an octet of decimal numbers, the value of each digit in each position would be 10^7=10000000, 10^6=1000000, 10^5=100000, 10^4=10000, 10^3=1000, 10^2=100, 10^1=10, and 10^0=1.
• From right to left a binary system has a ones place, a twos place, a fours place, a 16s place, a 32s place, a 64s place, a 128s place, etc. For comparison, from right to left a decimal system has a ones place, a tens place, a hundreds place, a thousands place, a ten thousands place, etc.
• Given an arbitrary binary number 1010, its decimal equivalent is 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 = 8 + 0 + 2 + 0 = 10. For comparison, the decimal number 170 = 1*10^2 + 7*10^1 + 0*10^0 = 100 + 70 + 0.
• A common binary number is an octet where each digit has been set to one: 11111111. In decimal that value is 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255.
• An easy way of manually converting a decimal value into a binary value is iterative division.
1. Take any positive decimal integer.
2. Divide by two.
3. Use the remainder portion to write the equivalent binary number.
4. If the integer portion is non-zero, then repeat from step 2, otherwise stop

EG: Given decimal number 170:

• 170/2 = 85 R 0. Therefore binary number so far is 0.
• 85/2 = 42 R 1. Therefore binary number so far is 10.
• 42/2 = 21 R 0. Therefore binary number so far is 010.
• 21/2 = 10 R 1. Therefore binary number so far is 1010.
• 10/2 = 5 R 0. Therefore binary number so far is 01010.
• 5/2 = 2 R 1. Therefore binary number so far is 101010.
• 2/2 = 1 R 0. Therefore binary number so far is 0101010.
• 1/2 = 0 R 1. Therefore binary number so far is 10101010.
• The integer portion of last division was 0 so for the decimal number 170, the binary equivalent is 10101010.

c/c++/java and many programming languages uses a shorthand to represent values in different bases. EG: This  decimal value int y = 12 is the same as this binary value int y = 0b1100, which is the same as this octal value int y = 0o14, which is the same as this hexadecimal value int y = 0x2C. Some system, like JavaScript distinguish decimal and octal integers by the absence of a leading zero. EG: decimal 12 is equal to octal 014.

## Common Powers

Common powers of 2.

 Power Decimal Decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... 31 32 .. 63 64 ... 127 128 1.00e+0 2.00e+0 4.00e+0 8.00e+0 1.60e+1 3.20e+1 6.40e+1 1.28e+2 2.56e+2 5.12e+2 1.02e+3 2.04e+3 4.09e+3 8.19e+3 1.63e+4 3.27e+4 6.55e+4 1.31e+5 2.62e+5 5.24e+5 1.04e+6 ... 2.14e+9 4.29e+9 ... 9.22e+18 1.84e+19 ... 1.70e+38 3.40e+38 1 2 4 8 16 32 64 128 256 512 1,024 2,048 4,096 8,192 16,384 32,768 65,536 131,072 262,144 524,288 1,048,576 ... 2,147,483,648 4,294,967,296 ... 9,223,372,036,854,775,808 18,446,744,073,709,551,616 ...

## Negative Numbers

Negative decimal are usually represented in this fashion:

... -4, -3, -2, -1, 0, 1, 2, 3, ...

Similarly, negative binary numbers could be represented in this fashion:

... -100, -11, -10, -1, 0, 1, 10, 11, ...

However the above is rarely done for binary numbers because it does not take advantage of a computers great ability to turn invert digits (i.e. turn 0s into 1s and vice versa).

The first thing you need to know is the value range that your integer calculations will cover. The maximum possible magnitude (M) will determine the number of binary digits you will need (N). If your calculations need negative numbers then M < 2N-1, otherwise M < 2N.

EG: If your calculations will always be between -810 and 710, then M = 8 and therefore N = 4. A four digit binary number is perfect because you will designate 010 to 710 as 00002 to 01112, and -810 to -110 as 10002 to 11112. Note that the left most binary digit of all the positive numbers is 0, while the left most binary digit is for all negative numbers is 1. In computer terminology, if the left most digit is the sign bit and the rest of the number is used for the magnitude, then you have a signed number. If a binary number is unsigned, then all the digits represent magnitude and a four digit binary number would represent 010 to 1510.

4 digit binary numbers
decimal signed
binary
decimal unsigned
binary
-8
-7
-6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
7
1000
1001
1010
1011
1100
1101
1110
1111
0000
0001
0010
0011
0100
0101
0110
0111
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

The decimal values are mapped to the signed binary values by the use of complements. If F is a subset of S, then F and its complement F' taken together is S. In this case the complements add up to zero, ie S = 0 and F + F' = 0. It turns out that calculating these complements are much easier to calculate in binary than for numbers of other bases because all you have to do is invert all the binary digits and add one (with the exception of zero). The complement of a signed binary number, other than zero, essentially negates the number.

EG: To negate  510, you would take  510 = 01012, invert to get 10102, and then add one to get 10112 = -510.
EG: To negate -510, you would take -510 = 10112, invert to get 01002, and then add one to get 01012 =  510.

There are two tricks involved in explaining why this magic works.

The first trick is that inverting binary digits is as simple as subtracting from the maximum binary number for those number of digits.

EG: Given x = a 4 digit binary number:

     1111         1111
-       x       - 1001
_________       ______
invertedX         0110

The second trick explains why the inverting plus adding one gets the right sign.

EG: Given x = a 4 digit binary number:

-x = -x
= -x + 10000     - 10000
= -x + 1111 + 1  - 10000
= (1111 - x + 1) - 10000
= xComplement    - 10000

So now to subtract in binary using complement, you simply add signed numbers together! EG:

Addition yielding number within acceptable range Subtraction yielding positive number Subtraction yielding negative number Addition yielding number outside of acceptable range
  5     0101
+ 2   + 0010
___   ______
7     0111 OK
  5     0101
- 2   + 1110
___   ______
3    10011 OK

If an answer has more than N digits then the digits on the left side are ignored until N digits are left.

  2     0010
- 5   + 1011
___   ______
-3     1101 OK
  5     0101
+ 5   + 0101
___   ______
10     1010 Not OK

The binary answer is -610 and is incorrect! The number of binary digits used should have been 5 or greater.

## Truth Tables

Truth tables are used in Boolean algebra or Boolean logic to display the results of logical operators in tabular format. The parameters and results are either true or false, where true is sometimes expressed as "Yes" or "1", and false is sometimes expressed as "No" or "0".

In computers frequently zero inputs --such as "no" and empty string ('')-- are treated as "false", while non-zero input --such as "yes", 17, and "dog"-- are treated as "true". Ambiguous input --such as undefined and null-- may be processed differently depending upon the system.

The NOT operator is unary (takes a single parameter), but can actually form its own truth table:

p
NOT p
logical negation
p
¬p
~p
!p
T F
F T

However most truth tables assume two parameters. Here are the 16 possible dual-parameter truth tables:

Truth Tables
p q 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Of the above 16 truth tables, only six are frequently encountered.

Truth Tables
p q 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
p NOR q
NOT (p OR q)
logical nor
p + q
joint denial
Webb-operation

True if both p and q are false.

p XOR q
exclusive or
p XNAN q
exclusive nand
p ⊕ q
p ⊻ q
exclusive disjunction

True if p and q are different.

p NAND q
NOT (p AND q)
not and
p ∙ q
p | q
Sheffer stroke
alternative denial

True if either p and q are false.

p AND q
logical conjunction
p ∙ q
p ∧ q

True if both p and q are true.

p XNOR q
exclusive nor
p XAND q
exclusive and
p ⩟ q

p IFF q
material equivalence
p ↔ q
p ⇔ q
biconditional

True p and q are the same.

p OR q
logical disjunction
p + q
p ∨ q
inclusive disjunction

True if either p or q is true.

0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Two of the gates are very important (9:AND and 15:OR). Each is paired with an inverse (8:NAND and 2:NOR respectively) known as an inverter, and they are denoted by the little circle called a bubble.

The other pair is 7:XOR and its invert 10:XNOR. The latter is also denoted by a bubble. These gates are often built from simpler gates.

12:IF is sometimes equivalent to the logical conditional "if-then" (aka material implication; material conditional; implies), and is usually expressed as p → q; p ⇒ q; p ⊃ q. The invert is 13:THEN, the logical condition "then-if", and is usually expressed as p ← q; p ⇐ q; p ⊂ q. This pair does not quite match natural language understanding and has led to work in multi-valued logic.

Here are some "combination tables" that look like "truth tables" and are probably more what the layman would expect:

For 2 binary variables, 4 combinations:

00
01
10
01
 0x 1x 00 10 01 11

EG:

 Male Female Boy Girl Man Woman

For 3 binary variables, 8 combinations:

000
001
010
011
100
101
110
111

These have ugly tables but triangular graphics works well. EG:

While truth tables usually deal with two-values (TRUE and FALSE), there are often truth tables with a a third value: NULL, which is equivalent to UNKNOWN. This is particularly common in databases and SQL.

pqp AND qp OR q
truetruetruetrue
truefalsefalsetrue
truenullnulltrue
falsetruefalsetrue
falsefalsefalsefalse
falsenullfalsenull
nulltruenulltrue
nullfalsefalsenull
nullnullnullnull
pNOT p
truefalse
falsetrue
nullnull

Page Modified: (Hand noted: ) (Auto noted: )