Skip to content
Mallikarjunarao Kosuri edited this page Jul 15, 2024 · 2 revisions

The add function performs the addition of two 8-bit integers x and y without using the + operator. Instead, it uses bitwise operations.

int8_t add(int8_t x, int8_t y)
{
    while (y != 0) {
        int8_t carry = x & y;
        x = x ^ y;
        y = carry << 1;
    }
    return x;
}

Explanation

  1. Bitwise AND (&): This operation finds all the bits where both x and y have 1s. This is used to find the carry bits.

  2. Bitwise XOR (^): This operation adds the bits of x and y without considering the carry. Essentially, it's like a half-adder.

  3. Left Shift (<<): This operation shifts the carry bits to the left by one position, preparing them to be added in the next iteration.

  4. Loop Until No Carry: The loop continues until there are no more carry bits (y becomes 0).

Example

Let's take an example where x = 3 (binary 00000011) and y = 5 (binary 00000101).

Step-by-Step Process

  1. Initial Values:

    • x = 00000011 (binary for 3)
    • y = 00000101 (binary for 5)
  2. First Iteration:

    • carry = x & y: 00000011 & 00000101 = 00000001
    • x = x ^ y: 00000011 ^ 00000101 = 00000110
    • y = carry << 1: 00000001 << 1 = 00000010
  3. Second Iteration:

    • carry = x & y: 00000110 & 00000010 = 00000010
    • x = x ^ y: 00000110 ^ 00000010 = 00000100
    • y = carry << 1: 00000010 << 1 = 00000100
  4. Third Iteration:

    • carry = x & y: 00000100 & 00000100 = 00000100
    • x = x ^ y: 00000100 ^ 00000100 = 00000000
    • y = carry << 1: 00000100 << 1 = 00001000
  5. Fourth Iteration:

    • carry = x & y: 00000000 & 00001000 = 00000000
    • x = x ^ y: 00000000 ^ 00001000 = 00001000
    • y = carry << 1: 00000000 << 1 = 00000000
  6. End Loop: Since y = 0, the loop exits, and x now contains the result, which is 8 in decimal (binary 00001000).

Bitwise Operations

Initial:
x = 00000011 (3)
y = 00000101 (5)

Iteration 1:
carry = x & y = 00000011 & 00000101 = 00000001
x = x ^ y     = 00000011 ^ 00000101 = 00000110
y = carry << 1                      = 00000001 << 1 = 00000010

Iteration 2:
carry = x & y = 00000110 & 00000010 = 00000010
x = x ^ y     = 00000110 ^ 00000010 = 00000100
y = carry << 1                      = 00000010 << 1 = 00000100

Iteration 3:
carry = x & y = 00000100 & 00000100 = 00000100
x = x ^ y     = 00000100 ^ 00000100 = 00000000
y = carry << 1                      = 00000100 << 1 = 00001000

Iteration 4:
carry = x & y = 00000000 & 00001000 = 00000000
x = x ^ y     = 00000000 ^ 00001000 = 00001000
y = carry << 1                      = 00000000 << 1 = 00000000

Result: x = 00001000 (8)

Example with Negative Numbers

Let's take an example where x = -3 and y = -5.

Step-by-Step Process

  1. Initial Values:

    • x = -3 (binary 11111101 in 2's complement representation)
    • y = -5 (binary 11111011 in 2's complement representation)
  2. First Iteration:

    • carry = x & y: 11111101 & 11111011 = 11111001
    • x = x ^ y: 11111101 ^ 11111011 = 00000110
    • y = carry << 1: 11111001 << 1 = 11110010
  3. Second Iteration:

    • carry = x & y: 00000110 & 11110010 = 00000010
    • x = x ^ y: 00000110 ^ 11110010 = 11110100
    • y = carry << 1: 00000010 << 1 = 00000100
  4. Third Iteration:

    • carry = x & y: 11110100 & 00000100 = 00000100
    • x = x ^ y: 11110100 ^ 00000100 = 11110000
    • y = carry << 1: 00000100 << 1 = 00001000
  5. Fourth Iteration:

    • carry = x & y: 11110000 & 00001000 = 00000000
    • x = x ^ y: 11110000 ^ 00001000 = 11111000
    • y = carry << 1: 00000000 << 1 = 00000000
  6. End Loop: Since y = 0, the loop exits, and x now contains the result, which is -8 in decimal (binary 11111000 in 2's complement representation).

Bitwise Operations

Initial:
x = 11111101 (-3)
y = 11111011 (-5)

Iteration 1:
carry = x & y = 11111101 & 11111011 = 11111001
x = x ^ y     = 11111101 ^ 11111011 = 00000110
y = carry << 1                      = 11111001 << 1 = 11110010

Iteration 2:
carry = x & y = 00000110 & 11110010 = 00000010
x = x ^ y     = 00000110 ^ 11110010 = 11110100
y = carry << 1                      = 00000010 << 1 = 00000100

Iteration 3:
carry = x & y = 11110100 & 00000100 = 00000100
x = x ^ y     = 11110100 ^ 00000100 = 11110000
y = carry << 1                      = 00000100 << 1 = 00001000

Iteration 4:
carry = x & y = 11110000 & 00001000 = 00000000
x = x ^ y     = 11110000 ^ 00001000 = 11111000
y = carry << 1                      = 00000000 << 1 = 00000000

Result: x = 11111000 (-8)

Explanation

  • Initial Values: The numbers -3 and -5 are represented in binary using 2's complement notation.
  • First Iteration: The carry is calculated as the bitwise AND of x and y. The sum without carry is calculated using bitwise XOR, and the carry is left-shifted.
  • Subsequent Iterations: The process is repeated until there are no more carry bits (when y becomes 0).
  • Result: The final value of x is 11111000, which is -8 in decimal (2's complement representation).

Why int8_t Instead of uint8_t

  1. Negative Numbers: Using int8_t allows the function to handle negative numbers. This is important for general-purpose addition where inputs might be signed integers.

  2. Sign Bit Handling: When shifting bits, especially when dealing with carry bits, using signed integers ensures proper handling of the sign bit. If uint8_t was used, there might be unexpected behaviour with sign extension.

Summary

The add function uses bitwise operations to add two integers by iteratively computing the carry and sum until there are no carry bits left. This method ensures correct addition without using the + operator.

Using int8_t allows handling both positive and negative numbers, making the function versatile for different inputs.

Clone this wiki locally