-
Notifications
You must be signed in to change notification settings - Fork 0
add
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;
}
-
Bitwise AND (
&
): This operation finds all the bits where bothx
andy
have1
s. This is used to find the carry bits. -
Bitwise XOR (
^
): This operation adds the bits ofx
andy
without considering the carry. Essentially, it's like a half-adder. -
Left Shift (
<<
): This operation shifts the carry bits to the left by one position, preparing them to be added in the next iteration. -
Loop Until No Carry: The loop continues until there are no more carry bits (
y
becomes0
).
Let's take an example where x = 3
(binary 00000011
) and y = 5
(binary 00000101
).
-
Initial Values:
-
x = 00000011
(binary for 3) -
y = 00000101
(binary for 5)
-
-
First Iteration:
-
carry = x & y
:00000011 & 00000101 = 00000001
-
x = x ^ y
:00000011 ^ 00000101 = 00000110
-
y = carry << 1
:00000001 << 1 = 00000010
-
-
Second Iteration:
-
carry = x & y
:00000110 & 00000010 = 00000010
-
x = x ^ y
:00000110 ^ 00000010 = 00000100
-
y = carry << 1
:00000010 << 1 = 00000100
-
-
Third Iteration:
-
carry = x & y
:00000100 & 00000100 = 00000100
-
x = x ^ y
:00000100 ^ 00000100 = 00000000
-
y = carry << 1
:00000100 << 1 = 00001000
-
-
Fourth Iteration:
-
carry = x & y
:00000000 & 00001000 = 00000000
-
x = x ^ y
:00000000 ^ 00001000 = 00001000
-
y = carry << 1
:00000000 << 1 = 00000000
-
-
End Loop: Since
y = 0
, the loop exits, andx
now contains the result, which is8
in decimal (binary00001000
).
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)
Let's take an example where x = -3
and y = -5
.
-
Initial Values:
-
x = -3
(binary11111101
in 2's complement representation) -
y = -5
(binary11111011
in 2's complement representation)
-
-
First Iteration:
-
carry = x & y
:11111101 & 11111011 = 11111001
-
x = x ^ y
:11111101 ^ 11111011 = 00000110
-
y = carry << 1
:11111001 << 1 = 11110010
-
-
Second Iteration:
-
carry = x & y
:00000110 & 11110010 = 00000010
-
x = x ^ y
:00000110 ^ 11110010 = 11110100
-
y = carry << 1
:00000010 << 1 = 00000100
-
-
Third Iteration:
-
carry = x & y
:11110100 & 00000100 = 00000100
-
x = x ^ y
:11110100 ^ 00000100 = 11110000
-
y = carry << 1
:00000100 << 1 = 00001000
-
-
Fourth Iteration:
-
carry = x & y
:11110000 & 00001000 = 00000000
-
x = x ^ y
:11110000 ^ 00001000 = 11111000
-
y = carry << 1
:00000000 << 1 = 00000000
-
-
End Loop: Since
y = 0
, the loop exits, andx
now contains the result, which is-8
in decimal (binary11111000
in 2's complement representation).
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)
-
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
andy
. 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
is11111000
, which is-8
in decimal (2's complement representation).
-
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. -
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.
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.