# Thread: Half Adder algorithm: 1) Why does 4 -3 = -15?; 2) Duplicate looping

1. ## Half Adder algorithm: 1) Why does 4 -3 = -15?; 2) Duplicate looping

During a Computer Science lecture, the teacher hinted in one of his slides that it is possible to make a program that would add integers together. So I tried at first on my own failing to think of a method. I then did a simple web search where I found some content, and recreated two programs. The first one is based on this sanfoundry tutorial.

Code:
```#include <stdio.h>

{
while(y != 0)
{
//Reset carry at the start of every iteration
int carry = x & y;

//x + y  =  X XOR Y
x = x ^ y;

//Carry from current iteration will be used for next iteration's calculations
y = carry << 1;

printf("\t x = %d \t y = %d\n", x, y);
}
return x;
}

int main()
{
int num1, num2;
printf("\nEnter two numbers to perform addition using bitwise operators: ");
scanf("%d%d", &num1, &num2);
return 0;
}```
The second one is based on Neso Academy bitwise addition with out '+' part two on a youtube tutorial.

Code:
```#include <stdio.h>

{
//int a, b;
while(y != 0)
{
//SUM
int sum = x ^ y;

//Carry
int carry = x & y;

//x
x = sum;

//Carry from current iteration will be used for next iteration's calculations
y = carry << 1;

printf("\t x = %d \t y = %d\n", x, y);
}
return x;
}

int main()
{
int num1, num2;
printf("\nEnter two numbers to perform addition using bitwise operators: ");
scanf("%d%d", &num1, &num2);
return 0;
}```
Instead of doing this on the computer, I first did it on paper, quickly finding the deadly combination of "4" and "-3", my scribblings:
Converting Decimal to Binary:
Code:
``` 4:
= 2^2 --> 0100

-3:
= -(+3)
+3 --> 0011
a) Complement positive number
~(0011)
== 1100

== 1100
+ 0001

Therefore
-3  ==  1101```
Once finished converting two arguments to binary, I start running through the algorithm:
Code:
``` Iteration 1:
int sum = x ^ y;
0100
^ 1101
sum = 1001

int carry = x & y;
0100
& 1101
carry = 0100

x = sum;
x = 1001;

y = carry << 1;
y = 0100 << 1;
y = 1000

Iteration 2:
int sum = x ^ y;
1001
^ 1000
sum = 0001

int carry = x & y;
1001
& 1000
carry = 1000

x = sum;
x  = 0001

y = carry << 1;
1000 << 1
y = 10000

Iteration 3:
int sum = x ^ y;
00001
^ 10000
sum = 10001

int carry = x & y;
00001
& 10000
carry = 00000

x = sum;
x  = 10001

y = carry << 1;
0 << 1
y = 0```
*** Since y == 0, while loop ends ***

Final answer is x = 10001, or decimal number -15.

How can the final answer of +4 - 3 = -15??? What did I do wrong??

Next I then try this algorithm on the computer, compiling by:

Code:
`\$ clang -99 -Wall -Wvla -Werror -fsanitize=address,undefined bitAddition_NESOAcademy_cast.c`
and run:

Code:
```\$ ./a.out
Enter two numbers to perform addition using bitwise operators: 4 -3```
Both get the following error:
Code:
```\$ ./a.out
Enter two numbers to perform addition using bitwise operators: -3 4
x = -7      y = 8
x = -15      y = 16
x = -31      y = 32
x = -63      y = 64
x = -127      y = 128
x = -255      y = 256
x = -511      y = 512
x = -1023      y = 1024
x = -2047      y = 2048
x = -4095      y = 4096
x = -8191      y = 8192
x = -16383      y = 16384
x = -32767      y = 32768
x = -65535      y = 65536
x = -131071      y = 131072
x = -262143      y = 262144
x = -524287      y = 524288
x = -1048575      y = 1048576
x = -2097151      y = 2097152
x = -4194303      y = 4194304
x = -8388607      y = 8388608
x = -16777215      y = 16777216
x = -33554431      y = 33554432
x = -67108863      y = 67108864
x = -134217727      y = 134217728
x = -268435455      y = 268435456
x = -536870911      y = 536870912
x = -1073741823      y = 1073741824
bitAddition_NESOAcademy.c:19:14: runtime error: left shift of 1073741824 by 1 places cannot be represented in type 'int'
x = -2147483647      y = -2147483648
x = 1      y = 0
Sum is 1```
I have found a stackexchange solution on this problem, and my interpretation is to use "unsigned integer" for carry, as follows:
Code:
```        //Carry
unsigned int carry = x & y;```
and even though this solves the "runtime error" as above, the rest of the behaviour is still the same extra duplicate loop till the end of the integers.

Code:
```\$ clang -99 -Wall -Wvla -Werror -fsanitize=address,undefined bitAddition_NESOAcademy_cast.c
\$ ./a.out
Enter two numbers to perform addition using bitwise operators: 4 -3
x = -7      y = 8
x = -15      y = 16
x = -31      y = 32
x = -63      y = 64
x = -127      y = 128
x = -255      y = 256
x = -511      y = 512
x = -1023      y = 1024
x = -2047      y = 2048
x = -4095      y = 4096
x = -8191      y = 8192
x = -16383      y = 16384
x = -32767      y = 32768
x = -65535      y = 65536
x = -131071      y = 131072
x = -262143      y = 262144
x = -524287      y = 524288
x = -1048575      y = 1048576
x = -2097151      y = 2097152
x = -4194303      y = 4194304
x = -8388607      y = 8388608
x = -16777215      y = 16777216
x = -33554431      y = 33554432
x = -67108863      y = 67108864
x = -134217727      y = 134217728
x = -268435455      y = 268435456
x = -536870911      y = 536870912
x = -1073741823      y = 1073741824
x = -2147483647      y = -2147483648
x = 1      y = 0

Sum is 1```
QUESTIONS
What am I doing wrong?

A. Paper calculations:
1) Why do I get 4 - 3 = -15?

B. Running program on the Computer:
1) Is the completion of so many loops what is supposed to happen?
2) Is there anyway to get rid of this duplicate loop calculations? 2. Why do I get 4 - 3 = -15?
Maybe you are supposed to ignore a bit that overflows (at least under certain conditions). Then the answer is 1, as expected. 3. An half adder is limited to one or two bit output. You are expected to ignore the other bits when you are using software.

The two bits are sum and carry; sometimes the carry does not exist. They are both limited to values of zero and one.

An half adder is a piece of hardware; this appears to be a program to simulate an it.

Edit: The inputs are also limited to zero and one!!

Tim S. 4. ## Is there anyway to get rid of this duplicate loop calculations?

Bitwise recursive addition of two integers - GeeksforGeeks Popular pages Recent additions binary addition, bit operations, carry, int, loop control 