Binary Arithmetic, Signed Numbers, ALU Design & Floating-Point

TAKEAWAYS:

• Binary arithmetic follows fixed rules for addition, subtraction, multiplication, and division, with carry/borrow propagation and overflow detection.
• Signed numbers are represented in sign-magnitude, 1’s complement, and 2’s complement formats, with 2’s complement being the most efficient for hardware.
• The Arithmetic Logic Unit (ALU) performs arithmetic and logical operations, combining registers, decoders, and multiplexers.
• Floating-point arithmetic uses IEEE 754 standards for representing real numbers, with precision trade-offs between mantissa and exponent.
• Booth’s algorithm optimizes multiplication/division of signed numbers by reducing the number of operations.
• Overflow and underflow must be detected in both integer and floating-point arithmetic to ensure correct results.

1. Binary Arithmetic Operations

Computers perform arithmetic using binary digits (0 and 1). The four fundamental operations are:

• Addition: Follows the same rules as decimal addition but with carry propagation.
• Subtraction: Performed as addition of the 2’s complement of the subtrahend.
• Multiplication: Uses shift-and-add or Booth’s algorithm for efficiency.
• Division: Uses restoring division or non-restoring division for signed numbers.

1.1 Binary Addition and Subtraction

Binary addition is straightforward:

  1 0 1 1  (11)
+ 0 1 1 0  (6)
-----------
 1 0 0 0 1  (17)

Subtraction is done by adding the 2’s complement of the subtrahend:

  1 0 1 1  (11)
- 0 1 1 0  (6)
-----------
 1 0 1 1  + 2’s complement of 6 (1 0 0 1 + 1 = 1 0 1 0)
-----------
 0 0 0 1  (1)

Overflow occurs if the result exceeds the bit-width (e.g., adding two positive numbers yields a negative result).

1.2 Binary Multiplication (Shift-and-Add)

Multiplication is done by shifting and adding:

   1 0 1 0  (10)
×    1 1 0 1  (13)
-----------
   1 0 1 0    (shift 0)
+ 1 0 1 0     (shift 1)
+ 0 0 0 0     (shift 2)
+ 1 0 1 0     (shift 3)
-----------
1 1 0 0 1 1 0  (130)

Booth’s algorithm reduces the number of additions by encoding sequences of 1s and 0s.

1.3 Binary Division (Restoring Division)

Division uses subtraction and shifting:

Dividend: 1 1 0 1 0 1  (101)
Divisor:   1 0 1 0      (10)
Quotient:  1 0 1 1      (11)
Remainder: 0 0 1 1      (3)

Steps:

1. Align divisor with dividend.
2. Subtract divisor from dividend.
3. Shift right and repeat until divisor fits no more.

2. Signed Number Representations

Computers represent signed numbers in three ways:

2’s complement is preferred because:

• No separate sign bit (simpler hardware).
• Direct subtraction (adding negative is same as adding positive).
• Overflow detection is straightforward.

2.1 Conversion Between Formats

• Sign-Magnitude → 2’s Complement:
  • If negative, invert bits and add 1.
  • Example: -5 (1 0 1 0) → 1 0 1 1 (-5 in 2’s complement).
• 1’s Complement → 2’s Complement:
  • Add 1 to the 1’s complement representation.

2.2 Overflow Detection in 2’s Complement

Overflow occurs if:

• Two positive numbers add to a negative result.
• Two negative numbers add to a positive result. Example:

  0 1 1 0  (+6)
+ 0 0 1 0  (+2)
-----------
 1 0 0 0  (-8) → Overflow!

3. Arithmetic Logic Unit (ALU)

The ALU performs arithmetic and logical operations. It consists of:

• Registers (to hold operands).
• Adders/Subtractors (for arithmetic).
• Multiplexers (to select operations).
• Control Unit (to manage operations).

3.1 ALU Block Diagram

flowchart LR
    A["Input A"] --> MUX1["Operation Selector"]
    B["Input B"] --> MUX2["Operation Selector"]
    MUX1 --> ADD["Adder"]
    MUX2 --> ADD
    ADD --> OUT["Result"]
    MUX1 --> SUB["Subtractor"]
    MUX2 --> SUB
    SUB --> OUT
    MUX1 --> AND["AND Gate"]
    MUX2 --> AND
    AND --> OUT
    MUX1 --> OR["OR Gate"]
    MUX2 --> OR
    OR --> OUT

Example ALU Operations:

3.2 ALU for Signed Numbers

• Uses 2’s complement arithmetic.
• Detects overflow using carry-out signals.
• Example: Adding -3 and 5 in 4-bit 2’s complement:

  -3: 1 1 0 1
  +5: 0 1 0 1
  -----------
  0 0 1 0  (2) → Correct!
  

4. Floating-Point Arithmetic (IEEE 754 Standard)

Floating-point numbers represent real numbers in the form:

± (Mantissa) × 2^(Exponent)

IEEE 754 Single-Precision (32-bit):

Example: 1.5 in IEEE 754:

• Binary: 1.1
• Normalized: 1.1 × 2^0
• Exponent: 0 + 127 = 127 (01111111)
• Mantissa: 10000000000000000000000 (implicit 1)
• Final: 0 01111111 10000000000000000000000

4.1 Floating-Point Operations

• Addition/Subtraction:
  1. Align exponents.
  2. Add/subtract mantissas.
  3. Normalize result.
• Multiplication/Division:
  1. Multiply/divide mantissas.
  2. Add/subtract exponents.
  3. Normalize.

Example: 1.5 + 0.5:

1.5: 1.1 × 2^0
0.5: 1.0 × 2^-1 → Align: 0.1 × 2^0
Sum: 1.1 + 0.1 = 10.0 × 2^0 → Normalize: 1.0 × 2^1 (2.0)

4.2 Floating-Point Overflow/Underflow

• Overflow: Exponent too large (e.g., 1.0 × 2^128).
• Underflow: Exponent too small (e.g., 1.0 × 2^-127 → denormalized or zero).

5. Real-World Applications

In the Real World

1. eSewa (Nepal):

   • Uses 2’s complement arithmetic for financial transactions (e.g., deducting Rs. 50 from Rs. 100).
   • Floating-point for displaying decimal amounts (e.g., Rs. 99.99).

2. Khalti (Digital Payments):

   • ALU operations validate transactions (e.g., checking if account_balance - transaction_amount ≥ 0).
   • Overflow detection prevents incorrect balances due to arithmetic errors.

3. Bank Loan Interest Calculation:

   • Uses floating-point arithmetic to compute monthly installments (e.g., principal × (rate/12) × (1 + rate)^n / ((1 + rate)^n - 1)).
   • 2’s complement ensures correct subtraction of payments from loan amounts.

4. Ncell Billing System:

   • Binary multiplication/division for calculating call durations and charges.
   • Overflow checks prevent billing errors in large transactions.

5. YouTube (Video Buffering):

   • Floating-point used in adaptive bitrate streaming to adjust video quality based on network speed.
   • ALU operations optimize buffer management (e.g., buffer_size - downloaded_data).

6. Daraz Order Processing:

   • Priority queues (implemented with ALU-controlled registers) manage order fulfillment.
   • 2’s complement used in inventory subtraction (e.g., stock - sold_items).

Exam Tip

1. Binary Arithmetic:

   • Always show carry/borrow propagation in addition/subtraction.
   • For multiplication/division, explain shifts and partial results.
   • Overflow detection is critical—practice with edge cases (e.g., MAX_INT + 1).

2. Signed Numbers:

   • Memorize 2’s complement rules (invert +1).
   • Compare sign-magnitude vs. 2’s complement in terms of hardware efficiency.
   • Overflow examples are common—practice adding/subtracting large numbers.

3. ALU Design:

   • Draw the block diagram and label components (adder, MUX, control signals).
   • Explain how operations are selected (e.g., 00 for add, 01 for subtract).
   • Signed ALU must handle overflow—mention carry-out checks.

4. Floating-Point:

   • Convert decimal to IEEE 754 (and vice versa) in exams.
   • Explain alignment and normalization in addition/multiplication.
   • Overflow/underflow definitions are key—know when they occur.

5. Worked Examples:

   • Always trace steps (e.g., Booth’s algorithm, restoring division).
   • Real-world ties (e.g., bank interest, eSewa transactions) can earn bonus marks.

Bit layout for single-precision floating-point numbers. (Image: Codekaizen, CC BY 3.0, via Wikimedia Commons)