Bases and conversion

A positional number system assigns each digit a weight equal to a power of the base. Binary uses base 2 (digits 0 and 1), octal base 8 (0 to 7), decimal base 10 and hexadecimal base 16 (0 to 9 and A to F, where A = 10 and F = 15).

Decimal to any base: divide repeatedly by the base and read the remainders from the last to the first. Any base to decimal: multiply each digit by its positional weight and add.

Because 8 = 2³ and 16 = 2⁴, binary converts to octal by grouping three bits, and to hexadecimal by grouping four, outward from the binary point (from the right for whole numbers). Octal ↔ hexadecimal is easiest through binary: expand each octal digit to 3 bits and regroup in 4s. Going through decimal also works, but it is slower.

Worked case: decimal 156 = 10011100 in binary (128 + 16 + 8 + 4). Grouped as 10 011 100, it is octal 234 (2 × 64 + 3 × 8 + 4 = 156). Grouped as 1001 1100, it is hexadecimal 9C (9 × 16 + 12 = 156).

Fractions and worked conversions

For the fractional part of a decimal number, multiply repeatedly by the base and collect the integer parts in order. 0.625 × 2 = 1.25 (1), 0.25 × 2 = 0.5 (0), 0.5 × 2 = 1.0 (1), so 0.625 = 0.101 in binary.

In the reverse direction, binary fractional places carry weights of 1/2, 1/4, 1/8 and so on. Hence 101101.101 = 32 + 8 + 4 + 1 + 0.5 + 0.125 = 45.625. Some decimal fractions, such as 0.1, have no finite binary form and must be rounded, which is the source of floating-point error.

Signed numbers and complements

The 1’s complement inverts every bit. The 2’s complement is the 1’s complement plus one. For n bits:

• sign-magnitude and 1’s complement cover −(2ⁿ⁻¹ − 1) to +(2ⁿ⁻¹ − 1);
• 2’s complement covers −2ⁿ⁻¹ to +(2ⁿ⁻¹ − 1).

For 4 bits that is ±7 versus −8 to +7; for 16 bits, ±32,767 versus −32,768 to +32,767. A single zero, and subtraction done by adding the complement, are why processors use 2’s complement.

Worked case: −45 in 8 bits. 45 = 00101101; inverted, 11010010 (the 1’s complement of 45); plus one, 11010011. Check: 00101101 + 11010011 = 1 00000000, and the carry out is discarded. In 2’s complement, a pattern beginning with 1 is negative. 11111111 is −1 in 2’s complement, −0 in 1’s complement and 255 as an unsigned number.

BCD, Excess-3, Gray code and ASCII

• BCD (8421) encodes each decimal digit separately in four bits: 59 = 0101 1001, whereas pure binary 59 = 111011. Codes 1010 to 1111 are invalid in BCD.
• Excess-3 adds 3 to each decimal digit before encoding: 59 becomes 1000 1100. It is self-complementing.
• Gray code changes exactly one bit between successive values. To convert binary to Gray, keep the leading bit, then XOR each pair of adjacent bits: binary 1011 → Gray 1110. The 3-bit sequence is 000, 001, 011, 010, 110, 111, 101, 100. Gray code is used in rotary encoders and in the ordering of Karnaugh map rows and columns.
• ASCII is a 7-bit code with 128 characters: uppercase A is 65 (41 hex) and lowercase a is 97 (61 hex), so the two cases differ by 32. “Extended ASCII” 8-bit sets are vendor code pages, not part of ASCII. Unicode covers the world’s scripts, and UTF-8 is its dominant encoding; UTF-8 keeps ASCII as its first 128 code points.

Boolean algebra and De Morgan

Boolean algebra works on 0 and 1 with three basic operations: AND (product), OR (sum) and NOT (complement).

The second distributive form has no counterpart in ordinary algebra. De Morgan reduces to one rule: break the bar and change the operator. It explains why a NAND gate is equivalent to an OR gate with inverted inputs.

Logic gates and universal gates

NAND outputs 0 only when all inputs are 1. NOR outputs 1 only when all inputs are 0. XOR outputs 1 when its two inputs differ; with more inputs it outputs 1 for an odd number of 1s, which is the basis of parity checking. XNOR is the equality gate.

NAND and NOR are universal: each one alone can implement any Boolean function. Minimum counts of two-input gates (checked by an exhaustive search, assuming no constant inputs):

Half adder and full adder

A half adder adds two bits and has no carry input: Sum = A ⊕ B and Carry = A·B (one XOR and one AND gate; five NAND gates if built from NAND alone). A full adder adds three bits (A, B and carry-in): Sum = A ⊕ B ⊕ C_in and Carry = AB + C_in(A ⊕ B), which equals AB + BC_in + AC_in. Two half adders and one OR gate form a full adder (nine NAND gates in the standard NAND-only design). Chaining n full adders gives an n-bit ripple-carry adder, whose carry delay grows with n.

Key points to remember

Frequently asked questions

What is the range of an n-bit 2’s complement number?

From −2^(n−1) to +(2^(n−1) − 1). For 8 bits this is −128 to +127. 1’s complement and sign-magnitude cover −(2^(n−1) − 1) to +(2^(n−1) − 1), which is ±127 for 8 bits.

How is a negative number written in 2’s complement?

Write the positive value in binary, invert every bit, and add 1. For example, −45 in 8 bits is 11010011.

What is the difference between BCD and Excess-3?

BCD codes each decimal digit in four bits (93 = 1001 0011). Excess-3 adds 3 to each digit first (93 = 1100 0110) and is self-complementing.

Why are NAND and NOR called universal gates?

Either gate alone can build NOT, AND, OR and therefore any Boolean function. For example, XOR needs four NAND gates or five NOR gates.

What are the equations of a full adder?

Sum = A ⊕ B ⊕ Cin and Carry = AB + Cin(A ⊕ B). Two half adders and one OR gate make a full adder.

Practice: 10 MCQs

Attempt all ten questions, then press Submit. The correct answer and a short explanation appear under every question, followed by your score analysis.

Verification notes

• Every conversion, code and complement on this page was recomputed by program. That covers 156 → 10011100 / 234₈ / 9C₁₆, 0.625 → 0.101, 101101.101 = 45.625, −45 → 11010011, −20 → 11101100, BCD/Excess-3 for 59 and 93, and Gray code for 1011.
• The Boolean laws and the full-adder equations were checked by complete truth tables. The minimum NAND/NOR gate counts were confirmed by an exhaustive circuit search over two-input gates.
• Standard references: M. Morris Mano, Digital Design / Digital Logic and Computer Design; ASCII as ANSI X3.4 (US-ASCII); the Unicode Standard (UTF-8).