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

  1. #1
    Registered User
    Join Date
    Mar 2015
    Posts
    9

    Question 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?
    Last edited by andrew.comly; 06-27-2020 at 02:17 PM. Reason: grammar

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    950
    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.
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    3,874
    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.
    Last edited by stahta01; 06-27-2020 at 04:31 PM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  4. #4
    null pointer Structure's Avatar
    Join Date
    May 2019
    Posts
    266

    Lightbulb

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

    Bitwise recursive addition of two integers - GeeksforGeeks
    "without goto we would be wtf'd"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 09-08-2018, 04:49 AM
  2. algorithm for duplicate file checking help
    By geekoftheweek in forum C Programming
    Replies: 1
    Last Post: 04-04-2009, 01:46 PM
  3. Monitor displaying half good / half bad
    By Hiyo in forum Tech Board
    Replies: 3
    Last Post: 12-16-2006, 10:06 PM
  4. Half Humanoid, half Chimpanzoid
    By Zewu in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 06-19-2004, 04:23 PM
  5. duplicate detection algorithm
    By Gustaff in forum C Programming
    Replies: 4
    Last Post: 01-28-2003, 12:26 PM

Tags for this Thread