Given two positive integers, return their sum without + operator

Problem statement is simple. Given two positive integers, return their sum without + operator. Reference: leetcode.com/problems/add-binary

Input: 5, 6

Output: 11

#include <stdint.h>
uint32_t Add(uint32_t x, uint32_t y)
{
    uint32_t sum = 0;
    //Implement logic

    return sum;
}

Actual intention of this problem is if you can implement Add function with logic gates. Let's think about truth table for half adder.

• Half Adder Truth Table

From truth table, you can find out carry = x & y and sum = x ^ y. However, we cannot use carry after just &. To take care of carry into result, it should be shifted 1 to left and add with next input bit iteration. This iteration will keep going until new carry is zero. Therefore, carry formula is (x & y) << 1

• Algorithm with an example

• Implementation and test

1. Created half_adder ceedling project

   ceedling module:create[half_adder]
   

2. half_adder.h

   #ifndef HALF_ADDER_H
   #define HALF_ADDER_H
   #include <stdint.h>
   uint32_t Add(uint32_t x, uint32_t y);
   #endif // HALF_ADDER_H
   

3. half_adder.c

   #include "half_adder.h"
   uint32_t Add(uint32_t x, uint32_t y)
   {
    uint32_t sum;
    uint32_t carry;
   
    do
    {
        sum = x ^ y;
        carry = (x & y) << 1;
        x = sum;
        y = carry;
    } while (carry != 0);
   
    return sum;
   }
   

4. test_half_adder.c

   #include "unity.h"
   #include "half_adder.h"
   void setUp(void)
   {
   }
   void tearDown(void)
   {
   }
   void test_half_adder_input5and6(void)
   {
    uint32_t x = 5;
    uint32_t y = 6;
    TEST_ASSERT_EQUAL(x+y, Add(x,y));
   }
   

5. run test and result

   ceedling test:half_adder
   

   

• Sample test case is not enough?

Yes, it is not enough because there are 4 cases with carry = 0 and another 4 cases with carry = 1. Example input 5 and 6 won't cover all those 8 cases. To prove the algorithm, you need to cover all 8 cases as minimum. I was able to derive two inputs to cover all 8 cases shown below:

Add test case in test_half_adder.c and re-test

void test_half_adder_input428and362(void)
{
    uint32_t x = 428;
    uint32_t y = 362;
    TEST_ASSERT_EQUAL(x+y, Add(x,y));
}