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.
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) { 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; }
Instead of doing this on the computer, I first did it on paper, quickly finding the deadly combination of "4" and "-3", my scribblings: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; }
Converting Decimal to Binary:
Once finished converting two arguments to binary, I start running through the algorithm:Code:4: = 2^2 --> 0100 -3: = -(+3) +3 --> 0011 a) Complement positive number ~(0011) == 1100 b) Add one == 1100 + 0001 Therefore -3 == 1101
*** Since y == 0, while loop ends ***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
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:
and run:Code:$ clang -99 -Wall -Wvla -Werror -fsanitize=address,undefined bitAddition_NESOAcademy_cast.c
Both get the following error:Code:$ ./a.out Enter two numbers to perform addition using bitwise operators: 4 -3
I have found a stackexchange solution on this problem, and my interpretation is to use "unsigned integer" for carry, as follows: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
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://Carry unsigned int carry = x & y;
QUESTIONSCode:$ 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
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?
