Thread: 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>

int bitwiseadd(int x, int y)
{
    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);
    printf("\nSum is %d", bitwiseadd(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 bitwiseadd(int x, int y)
{
    //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);
    printf("\nSum is %d", bitwiseadd(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
         
        b) Add one
           == 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'
    SUMMARY: AddressSanitizer: undefined-behavior bitAddition_NESOAcademy.c:19:14 in 
         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?

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.

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.

Is there anyway to get rid of this duplicate loop calculations?

Bitwise recursive addition of two integers - GeeksforGeeks