CareerCup

public static String addBinary(String s1,String s2) {
        if(s1 == null || s2 == null) {
            return "";
        }
        int first = s1.length()-1;
        int second = s2.length()-1;
        StringBuilder sb = new StringBuilder();
        int carry =0 ;
        int curr = 0;
        while(first >=0 || second >=0) {
            int firstValue = (first < 0) ? 0 : s1.charAt(first)-'0';
            int secondValue =  (second < 0)? 0: s2.charAt(second)-'0';
            int sum = firstValue + secondValue + carry;

            carry = sum >> 1;
            sum = sum & 1;

            sb.insert(0, (sum==0 ? '0' : '1'));
            first--;
            second--;
        }
        return sb.toString();
    }

//Add two strings of binary char
//String can be of diff length

void reverse(char arr[], int low, int high)
{

  while(low < high)
  {
     arr[low] = arr[low]^arr[high];
     arr[high] = arr[low]^arr[high];
     arr[low] = arr[low]^arr[high];
     low++;
     high--;
    
  }

}

char* AddTwoString(char* str1, char* str2)
{ 
    int s1 = strlen(str1);
    reverse(str1,0,s1-1);

    int s2 = strlen(str2);
    reverse(str2,0,s2-1);

    int s = (s1 > s2 ? s1 : s2)+1;

    char *p = new char[s];

    int i = 0;
    int j = 0;
    int k = -1;
    
    int carry = 0;
    
    int bit1 = 0;
    int bit2 = 0;

    while(i < s1 && j < s2)
    {
      
       bit1 = str1[i++] - '0';
       bit2 = str2[j++] - '0';
       p[++k] = (bit1^bit2^carry) + '0';
       carry = ((bit1&bit2)^carry)^((bit1^bit2)&carry);
    }


   

    while(i < s1)
    {
       bit1 = str1[i] - '0'; 
       p[++k] = bit1^carry + '0';
       carry = bit1*carry;
       i++;
    }

    while(j < s2)
    {
       bit2 = str2[j] - '0'; 
       p[++k] = bit2^carry;
       carry = bit2*carry;
       j++;
    }

  
    if(carry == 1)
    {
       p[++k] = '1';
    }

    reverse(p,0,k);
    
    p[++k] = '\0';  
    return p;
}
int main()
{
   char arr1[] = "10110101";
   char arr2[] = "11001110";
   char* sumStr = AddTwoString(arr1,arr2)<<endl;
  cout<<sumPtr<<endl;

 delete []sumPtr;//delete memory that allocated using new
   return 0;
}

Code in c:

#include <stdio.h>
#include <conio.h>
#include <string.h>
static int k;
void reve(char *str,int j)
{
    int i=0;
    while(i<j)
    {
        char temp=str[i];
        str[i++]=str[j];
        str[j--]=temp;
    }
}

void add2(char a,char b,char *sum2)
{
    if(a=='0'&&b=='1')
	{
		sum2[0]='1',sum2[1]='0';
	}
	else if(a=='1'&&b=='1')
	{
		sum2[0]='1',sum2[1]='1';
	}
	return sum2;
}

void add3(char a,char b,char c,char *sum)
{
	if(a=='0'&&b=='0'&&c=='0')
	{
		sum[0]='0';
		sum[1]='0';
	}
	else if((a=='1'&&b=='0'&&c=='0')||(a=='0'&&b=='1'&&c=='0')
		||(a=='0'&&b=='0'&&c=='1'))
	{
		sum[0]='1';
		sum[1]='0';
	}
	else if((a=='1'&&b=='1'&&c=='0')||(a=='0'&&b=='1'&&c=='1')
		||(a=='1'&&b=='0'&&c=='1'))
	{
		sum[0]='0';
		sum[1]='1';
	}
	else if(a=='1'&&b=='1'&&c=='1')
	{
		sum[0]='1';
		sum[1]='1';
	}
}

void traverse(char *str1,char *str2,char *s,char *str3,char c)
{
    int i,j;
    for(i=strlen(str2)-1,j=strlen(str1)-1;i>=0;i--,j--)
		{
			add3(str1[j],str2[i],c,s);
			if(s[1]=='0')
				str3[k++]=s[0];
			else if(s[1]=='1')
			{
				str3[k++]=s[0];
				c='1';
			}
		}
		for(i=j;i>=0;i--)
		{
			if(c=='1')
			{
				add2(str1[i],c,s);
				if(s[1]=='0')
					str3[k++]=s[0];
				else
				{
					str3[k++]=s[0];
					c='1';
				}
			}
			else
			{
				str3[k++]=str1[i];
			}
		}

}
char *sum(char *str1,char *str2)
{
	char str3[30],s[2],c='0';
	int j,i;
	if(strlen(str1)>strlen(str2))
	{
        traverse(str1,str2,s,str3,c);
	}
	else if(strlen(str1)<strlen(str2))
    {
         traverse(str2,str1,s,str3,c);
    }
    else
    {
        int i,j;
        for(i=strlen(str2)-1,j=strlen(str1)-1;i>=0&&j>=0;i--,j--)
		{
			add3(str1[j],str2[i],c,s);
			if(s[1]=='0')
				str3[k++]=s[0];
			else if(s[1]=='1')
			{
				str3[k++]=s[0];
				c='1';
			}
		}
		if(c=='1')
            str3[k++]=c;
    }
	reve(str3,k-1);
	for(i=0;i<k;i++)
        printf("%c",str3[i]);
    return str3;
}
int main()
{
	char str1[]="1001";
	char str2[]="100";
    char *str3=sum(str1,str2);
}

Solution in Objective-C, leveraging the "category" feature of such language, that enables to aggregate methods to existing classes. In this case, the approach consists in aggregating a sumBinaryString:(NSString*) instance method to class NSString. The complexity is linear --i.e., O(n).

Tests first:

#import <XCTest/XCTest.h>
#import "NSString+Binary.h"

@interface CSPBinaryStringSumTests : XCTestCase

@end

@implementation CSPBinaryStringSumTests {
    NSError* error_;
}

- (void)setUp
{
    [super setUp];
    error_ = nil;
}

- (void)tearDown
{
    error_ = nil;
    [super tearDown];
}

- (void)testNormalCase
{
    NSString *op1 = @"101", *op2 = @"11";
    XCTAssertEqualObjects(@"1000", [op1 sumBinaryString:op2]);
}

- (void)testNullCase
{
    XCTAssertNil([@"1" sumBinaryString:nil]);
}

- (void)testUnusualYetValidInput
{
    NSString *op1 = @"0000000000000101", *op2 = @"0000000000000000000000000011";
    XCTAssertEqualObjects(@"1000", [op1 sumBinaryString:op2]);
}

- (void)testZeroes
{
    NSString *op1 = @"0000000000000", *op2 = @"0000000000000000000000000011";
    XCTAssertEqualObjects(@"11", [op1 sumBinaryString:op2]);

    op1 = @"0000000000000101", op2 = @"00000000000000000000000000";
    XCTAssertEqualObjects(@"101", [op1 sumBinaryString:op2]);

    op1 = @"0000000000000", op2 = @"00000000000000000000000000";
    XCTAssertEqualObjects(@"0", [op1 sumBinaryString:op2]);
}

- (void)testInvalidBinaries
{
    NSString *op1 = @"I'm not a binary string";
    XCTAssertNil([op1 sumBinaryString:@"101" error:&error_]);

    XCTAssertNil([@"101" sumBinaryString:@"I'm not either" error:&error_]);
}

- (void)testHugeInput
{
    NSString *op1 = @"1010101010101010101010101010101010101010" \
    @"0101010101010101010101010101010101010101" \
    @"1010101010101010101010101010101010101010" \
    @"0101010101010101010101010101010101010101" \
    @"1010101010101010101010101010101010101010" \
    @"0101010101010101010101010101010101010101",
    *op2 = @"101010101010101010101010101010101010101" \
    @"1010101010101010101010101010101010101010" \
    @"0101010101010101010101010101010101010101" \
    @"1010101010101010101010101010101010101010" \
    @"0101010101010101010101010101010101010101" \
    @"1010101010101010101010101010101010101011",
    *expected = @"10000000000000000000000000000000000000000" \
    @"0000000000000000000000000000000000000000" \
    @"0000000000000000000000000000000000000000" \
    @"0000000000000000000000000000000000000000" \
    @"0000000000000000000000000000000000000000" \
    @"0000000000000000000000000000000000000000";

    XCTAssertEqualObjects(expected, [op1 sumBinaryString:op2 error:&error_]);
}

@end

Category header:

#import <Foundation/Foundation.h>

extern NSString * const NSStringBinaryErrorDomain;

@interface NSString (Binary)

/**
 * Sums the operand to the self string, assuming both contain only binary chars.
 * @param operand the binary number, represented as a string of '1's and '0's.
 * @return a new string containing the binary repressentation of the sum of the
 * input. Nil in case some error happens with the input.
 */
- (NSString*)sumBinaryString:(NSString*)operand;

/**
 * Sums the operand to the self string, assuming both contain only binary chars.
 * @param operand the binary number, represented as a string of '1's and '0's.
 * @param error a reference to an NSError* where the reasons for failure will be
 * left, if a failure happened at all.
 * @return a new string containing the binary repressentation of the sum of the
 * input. Nil in case some error happens with the input (check error in such 
 * case).
 */
- (NSString*)sumBinaryString:(NSString*)operand error:(NSError* __strong *) error;

@end

Category implementation:

#import "NSString+Binary.h"

NSString * const NSStringBinaryErrorDomain = @"NSStringBinaryDomain";

// Convenience function that assigns the longest string to the output parameter
// longest, the shortest to shortest.
// Returns the length of the longest.
NSUInteger assignLongestAndShortest(NSString **longest, NSString **shortest,
                                    NSString *str1, NSString *str2)
{
    if ([str1 length] > [str2 length]) {
        *longest = str1; *shortest = str2;
    } else {
        *longest = str2; *shortest = str1;
    }

    return [*longest length];
}

@implementation NSString (Binary)

- (NSString*)sumBinaryString:(NSString*)operand
{
    return [self sumBinaryString:operand error:nil];
}

- (NSString*)sumBinaryString:(NSString*)operand error:(NSError* __strong *)error
{
    NSString *result = nil;
    NSInteger statusCode = 0;
    id statusObject;

    if (operand) {
        NSString *longest, *shortest;
        // we'll work on a temporaty C-array whose length is the length of the
        // longest input string plus 1 for a potential carry.
        NSUInteger bufferLength = assignLongestAndShortest(&longest, &shortest,
                                                           self, operand) + 1;
        unichar *buffer = new unichar[bufferLength]();

        @try {
            NSUInteger index;
            BOOL carry;

            // this algorithm iterates with O(n) where n is the length of the
            // longest string. It iterates backward over the strings, in two
            // phases.
            // The first phase is while both strings have common positions
            // covered, starting from the end.
            for (index = 1, carry = NO; index <= [shortest length]; ++index) {
                // Both characters are compared to calculate the resulting some
                // at that position, taking into account a potential carry from
                // the previous iteration.
                switch ([longest characterAtIndex:([longest length] - index)]) {
                    case '0':
                        switch ([shortest characterAtIndex:([shortest length] - index)]) {
                            case '0':
                                buffer[bufferLength - index] = carry ? '1' : '0';
                                carry = NO;
                                break;

                            case '1':
                                buffer[bufferLength - index] = carry ? '0' : '1';
                                break; // in this scenario, carry wouldn't change

                            default:
                                // If the shortest string has other than 1 or 0,
                                // the string is a malformed binary.
                                statusCode = 200;
                                statusObject = shortest;
                                break;
                        }
                        break;
                        
                    case '1':
                        switch ([shortest characterAtIndex:([shortest length] - index)]) {
                            case '0':
                                buffer[bufferLength - index] = carry ? '0' : '1';
                                break;

                            case '1':
                                buffer[bufferLength - index] = carry ? '1' : '0';
                                carry = YES;
                                break;

                            default:
                                statusCode = 200;
                                statusObject = shortest;
                                break;
                        }
                        break;

                    default:
                        // the longest is a malformed binary string
                        statusCode = 200;
                        statusObject = longest;
                        break;
                }
                // short-circuit if statusCode isn't 0 anymore.
                if (statusCode) break;
            }

            if (!(statusCode)) {
                // Second phase of the loop over longest: this portion only covers
                // the most-significant section of the longest that doesn't have
                // counterpart in the shortest.
                for (; index <= [longest length]; ++index) {
                    switch ([longest characterAtIndex:([longest length] - index)]) {
                        case '0':
                            buffer[bufferLength - index] = carry ? '1' : '0';
                            carry = NO;
                            break;

                        case '1':
                            buffer[bufferLength - index] = carry ? '0' : '1';
                            carry = YES;
                            break;

                        default:
                            statusCode = 200;
                            statusObject = longest;
                            break;
                    }
                    if (statusCode) break;
                }

                if (!(statusCode)) {
                    // last check after finishing with the longest: is there any
                    // carry left? If so, turn on the first char.
                    buffer[0] = carry ? '1' : '0';
                    carry = NO;

                    // Now, let's skip all '0' until finding the canonical most
                    // significant '1'.
                    for (index = 0;
                         (buffer[index]) == '0' && (index < bufferLength - 1);
                         ++index);

                    result =
                    [NSString stringWithCharacters:buffer+index
                                            length:bufferLength - index];
                }
            }
        }
        @finally {
            delete[] buffer;
        }
    } else {
        // The operand is nil, sum skipped.
        statusCode = 100;
    }

    if ((statusCode) && (error)) {
        [self p_populateError:error forCode:statusCode andObject:statusObject];
    }

    return result;
}

// Produces an NSError in the NSStringBinaryErrorDomain domain based on the
// status code received as parameter.
- (void) p_populateError:(NSError* __strong *)error
                 forCode:(NSInteger)code
               andObject:(id)object
{
    if (error) {
        NSMutableDictionary *userInfo = [NSMutableDictionary dictionary];

        switch (code) {
            case 100:
                [userInfo setObject:@"Binary sum skipped."
                             forKey:NSLocalizedDescriptionKey];
                [userInfo setObject:@"Operand is nil"
                             forKey:NSLocalizedFailureReasonErrorKey];
                [userInfo setObject:@"Provide a binary operand"
                             forKey:NSLocalizedRecoverySuggestionErrorKey];
                break;

            case 200:
                [userInfo setObject:@"Binary sum aborted."
                             forKey:NSLocalizedDescriptionKey];
                [userInfo setObject:[NSString stringWithFormat:
                                     @"Operand isn't binary: \"%@\"", object]
                             forKey:NSLocalizedFailureReasonErrorKey];
                [userInfo setObject:@"Provide a binary operand"
                             forKey:NSLocalizedRecoverySuggestionErrorKey];
                break;
                
            default:
                [userInfo setObject:@"Undetermined error"
                             forKey:NSLocalizedDescriptionKey];
        }

        *error = [NSError errorWithDomain:NSStringBinaryErrorDomain
                                     code:code userInfo:userInfo];
    }
}

@end

A simple O(n) solution:
=================================================

package strings;

public class AddBinaryStrings {

	public void addBinaryStrings(String a, String b){
		
		int ea = a.length() - 1;
		int eb = b.length() - 1;
		
		// Resulting string will be of length more than one or equal to max string
		int i = Math.max(ea, eb) + 1;
		char[] finalStr = new char[i + 1];
		
		int carry = 0;
		
		while( i > 0){
			
			int curVal = 0;
			
			if(ea >= 0)
				curVal += a.charAt(ea) - '0';
			
			if(eb >= 0)
				curVal += b.charAt(eb) - '0';
			
			curVal += carry;
			
			// Make sure all the possible sums - 0,1,2,3 are taken care of
			if(curVal == 1){
				
				finalStr[i] = '1';
			}
			else if(curVal == 2){
				finalStr[i] = '0';
				carry = 1;
			}
			else if(curVal == 3){
				finalStr[i] = '1';
				carry = 1;
			}
			else{
				finalStr[i] = '0';
			}
			
			i--;
			ea--;
			eb--;
		}
		
		// Make sure carry from the last operation is taken care of
		if(carry == 1)
			finalStr[0] = '1';
		else
			finalStr[0] = '0';
		
		
		System.out.println(String.valueOf(finalStr));
	}
	
	public static void main(String[] args){
		
		AddBinaryStrings astr = new AddBinaryStrings();
		
		astr.addBinaryStrings("11", "00");
		astr.addBinaryStrings("1100", "01");
		astr.addBinaryStrings("111", "11");
		
	}
	
}

int oneInt = Integer.parseInt(oneString, 2);
		int twoInt = Integer.parseInt(twoString, 2);
		
		int sum = oneInt + twoInt;
		return Integer.toBinaryString(sum);

public static String sum(String s1,String s2){
if(s1.length()==0||s2.length()==0) return s1.length()==0 ? s1 : s2;
else{
int carry=0;int sum=0;
StringBuffer sb=new StringBuffer();
int first=s1.length()-1;int second=s2.length()-1;
while(first>=0||second>=0){
int firstValue=first<0? 0 : Integer.valueOf(s1.charAt(first));
int secondValue=second<0? 0 : Integer.valueOf(s2.charAt(second));
sum=firstValue+secondValue+carry;
carry=sum>>1;
sum&=1;
sb.append(sum==0? "0":"1");
first--;second--;
}
return sb.toString();
}

public class BinaryConverter {
	public static void main(String[] args) {
		 String str1 = "1010101010";
		 String str2 = "0110";
		 int number1 = getIntegerFromBinary(str1);
		 int number2 = getIntegerFromBinary(str2);
		 System.out.println("The sum is :: "+ (number1+number2));
	}

	private static int getIntegerFromBinary(String str) {
		char[] arr = str.toCharArray();
		int sum = 0;
		for(int i = arr.length-1,j=0;i>=0;i--,j++){
			if(arr[i] == '1')
				sum = (int) (sum + Math.pow(2, j));
		}
		return sum;
	}
}

public static String Add(String s1, String s2)
{
StringBuilder result = new StringBuilder();

if(s1 == null && s2 == null)
{
result = null;
}
else if(s1 == null && s2 != null)
{
result.append(s2);
}
else if(s1 != null && s2 == null)
{
result.append(s1);
}
else
{
int carry = 0;

int s1EndIndex = s1.length() - 1;
int s2EndIndex = s2.length() - 1;

while(s1EndIndex >= 0 || s2EndIndex >= 0)
{
int s1Char = ( s1EndIndex < 0) ? 0 : s1.charAt(s1EndIndex) - '0';
int s2Char = ( s2EndIndex < 0) ? 0 : s2.charAt(s2EndIndex) - '0';

int sum = s1Char + s2Char + carry;

if(sum == 0)
{
result.insert(0, '0');
}
else if(sum == 1)
{
result.insert(0, '1');
}
else if(sum == 2)
{
result.insert(0, '0');
carry = 1;
}
else
{
result.insert(0, '1');
carry = 1;
}

s1EndIndex--;
s2EndIndex--;
}

if(carry == 1)
{
result.insert(0, '1');
}

}

return result.toString();

}

PHP:

function getSumOfBinaryNumbers($num1, $num2)
{
	$num1Digits = str_split($num1);
	$num1Size = count($num1Digits);
	$num2Digits = str_split($num2);
	$num2Size = count($num2Digits);
	$count = abs($num1Size - $num2Size);
	if ($num1Size > $num2Size) {
		for ($i = 0; $i < $count; $i++) {
			array_unshift($num2Digits, '0');
		}
	} else if ($num1Size < $num2Size) {
		for ($i = 0; $i < $count; $i++) {
			array_unshift($num1Digits, '0');
		}
	}
	$resultDigits = array();
	$higherBitShift = false;
	$shiftedBit = $resultDigit = 0;
	$size = count($num1Digits) - 1;
	for ($i = $size; $i >= 0; $i--) {
		// 1 + 1
		if ($num1Digits[$i] == 1 && $num2Digits[$i] == 1) {
			$resultDigit = 0 + $shiftedBit;
			$higherBitShift = true;
			$shiftedBit = 1;
		}
		// 1 + 0 or 0 + 1 or 0 + 0
		else {
			$resultDigit = (int) $num1Digits[$i] + (int) $num2Digits[$i];
			if ($resultDigit == 1 && $higherBitShift) {
				$resultDigit = 0;
				$shiftedBit = 1;
				$higherBitShift = true;
			} else {
				$resultDigit += $shiftedBit;
				$higherBitShift = false;
				$shiftedBit = 0;
			}
		}
		$resultDigits[$i] = $resultDigit;
		if ($higherBitShift && $i == 0) {
			array_push($resultDigits, 1);
		}
	}

	return ltrim(implode('', array_reverse($resultDigits)), '0');
}

void BinaryAddition(string& str1,string& str2, string& strFinal)
{
int nCarry=0;
int nFirstLength=str1.length();
int nSecondLength=str2.length();
int nFirstNumber=0;
int nSecondNumber=0;
int nSum=0;
while((nFirstLength>0) && (nSecondLength>0))
{
nFirstNumber=str1.at(nFirstLength-1)-'0';
nSecondNumber=str2.at(nSecondLength-1)-'0';
nSum=nFirstNumber+nSecondNumber+nCarry;
nCarry=nSum>>1;
nSum=nSum & 1;
(nSum>0)?strFinal.insert(0,"1"):strFinal.insert(0,"0");
nFirstLength--;
nSecondLength--;
}
while(nFirstLength>0)
{
nFirstNumber=str1.at(nFirstLength-1)-'0';
nSum=nFirstNumber+nCarry;
nCarry=nSum>>1;
nSum=nSum & 1;
(nSum>0)?strFinal.insert(0,"1"):strFinal.insert(0,"0");
nFirstLength--;
}
while(nSecondLength>0)
{
nSecondNumber=str2.at(nSecondLength-1)-'0';
nSum=nSecondNumber+nCarry;
nCarry=nSum>>1;
nSum=nSum & 1;
(nSum>0)?strFinal.insert(0,"1"):strFinal.insert(0,"0");
nFirstLength--;
}
if(nCarry!=0)
strFinal.insert(0,"1");
}

N=length of one string, M=length of the other string. O(max(N,M)) time complexity and O(max(N,M) space complexity algorithm. I didn't insert sum into the first position of the result string because it may cause reallocation and copying and in result, complexity may become O(max(N,M)^2). Instead, I append the sum and return the reversed string.

auto add2 = [](const string& ons1, const string& ons2) {
	string ret;
	int carry = 0;
	auto ns1 = ons1.c_str(), ns2 = ons2.c_str();
	int i = ons1.length()-1, j = ons2.length()-1;
	if (ons1.length() < ons2.length()) {
		swap(ns1, ns2);
		swap(i,j);
	}
	ret.reserve(i+2); // pre-allocate space for longer string length + possible last carry to avoid reallocation
	int n1 = 0, n2 = 0;
	for (; i >= 0; --i, --j) {
		n1 = ns1[i] - '0';
		n2 = j >= 0 ? ns2[j] - '0' : 0;
		ret.push_back((n1 ^ n2 ^ carry) + '0');
		carry = (n1 & n2) | (n1 & carry) | (n2 & carry);
	}
	if (carry) {
		ret.push_back(carry + '0');
	}
	reverse(ret.begin(), ret.end());
	return ret;
};

Two more words:
1. Made ns1 the longer string to avoid additional O(max(N,M)) comparisons for i >= 0 when calculating n1 and comparisons for j >= 0 loop exit condition.
2. Computed sum and carry using only bit operations which is faster than arithmetic operations.

This problem is kinda simple and here is my Java code to solve this problem -:

public class BinaryStringAdder {
	
	public static ArrayList<Integer> binaryAdder(ArrayList<Integer> num1, ArrayList<Integer> num2){
		Collections.reverse(num1);
		Collections.reverse(num2);
		int carry = 0;
		ArrayList<Integer> sum = new ArrayList<Integer>();
		for(int i = 0; i < num2.size(); ++i){
			int temp = num1.get(i) + num2.get(i) + carry;
			sum.add(temp%2);
			carry = temp/2;
		}
		for(int i = num2.size(); i < num1.size(); ++i){
			int temp = num1.get(i) + carry;
			sum.add(temp%2);
			carry = temp/2;
		}
		
		if(carry != 0)
			sum.add(carry);
		
		Collections.reverse(sum);
		
		return sum;
	}
	
	public static void main(String[] args) throws IOException{		
		ArrayList<Integer> sum;
		if(biNum1.size() >= biNum2.size())
			sum = binaryAdder(biNum1, biNum2);
		else
			sum = binaryAdder(biNum2, biNum1);
		
		for(int i = 0; i < sum.size(); ++i)
			System.out.print(sum.get(i));
	}
}

string addBinaryStrings(string a, string b)
{
    string c;
    int carry = 0;
    int lena = a.length(), lenb = b.length();
    int i=lena-1, j=lenb-1, k=max(lena, lenb)-1;

    c.resize(k+1, '0');

    while (i>=0 && j>=0) {
        c[k] = ((a[i]-'0') ^ (b[j]-'0') ^ carry) + '0';
        carry = (carry + (a[i]-'0') + (b[j]-'0')) > 1 ? 1 : 0;
        i--,j--,k--;
    }   

    while (i>=0) {
        c[k] = (carry ^ (a[i]-'0')) + '0';
        carry = (carry+(a[i]-'0')) > 1 ? 1 : 0;
        i--,k--;
    }   

    while (j>=0) {
        c[k] = (carry ^ (b[j]-'0')) + '0';
        carry = (carry+(b[j]-'0')) > 1 ? 1 : 0;
        j--,k--;
    }

    if (carry) return "1" + c;

    return c;
}

Code in java. Complexity is O(N)

public String addBinary(String n1, String n2){
int carry = 0;
int l = Math.min(n1.length(), n2.length());
String answer = "";

for(int i=1; i <= l ; i++){
int digit = (n1.charAt(n1.length()-i) - '0') ^ (n2.charAt(n2.length()-i)- '0') ^ carry;
carry = (carry ==0)?(n1.charAt(n1.length()-i) - '0') & (n2.charAt(n2.length()-i)- '0'):
((n1.charAt(n1.length()-i) - '0') | (n2.charAt(n2.length()-i)- '0')) & carry;
answer = digit+ answer;
}


if(n1.length() > n2.length()){

for(int i= l+1; i <n1.length() ; i++){
int digit = (n1.charAt(n1.length()-i) - '0') ^ carry;
carry = carry & (n1.charAt(n1.length()-i) - '0');
answer = digit+ answer;
}
}
else if(n1.length() < n2.length()){

for(int i= l+1; i <=n2.length() ; i++){
int digit = (n2.charAt(n2.length()-i) - '0') ^ carry;
carry = carry & (n2.charAt(n2.length()-i) - '0');
answer = digit+ answer;
}
}

answer = carry+ answer;

return answer;

}

Code in Java, complexity is O(N)

public String addBinary(String n1, String n2){
		int carry = 0;
		int l = Math.min(n1.length(), n2.length());
		String answer = "";
		
		for(int i=1; i <= l ; i++){
			int digit = (n1.charAt(n1.length()-i) - '0') ^ (n2.charAt(n2.length()-i)- '0') ^ carry;
			carry = (carry ==0)?(n1.charAt(n1.length()-i) - '0') & (n2.charAt(n2.length()-i)- '0'):
				((n1.charAt(n1.length()-i) - '0') | (n2.charAt(n2.length()-i)- '0')) & carry;
			answer = digit+ answer;
		}
		

		if(n1.length() > n2.length()){
			
			for(int i= l+1; i <n1.length() ; i++){
				int digit = (n1.charAt(n1.length()-i) - '0') ^ carry;
				carry = carry & (n1.charAt(n1.length()-i) - '0');
				answer = digit+ answer;
			}
		}
		else if(n1.length() < n2.length()){
			
			for(int i= l+1; i <=n2.length() ; i++){
				int digit = (n2.charAt(n2.length()-i) - '0') ^ carry;
				carry = carry & (n2.charAt(n2.length()-i) - '0');
				answer = digit+ answer;
			}
		}

		answer = carry+ answer;

		return answer;
		
	}

public long sum(String x, String y)
{
   if(x == null || y == null)
      throw new IllegalArgumentException("X or/and y is null");
   if(x.length > 64 || y.length > 64)
      throw new IllegalArgumentException("xlen, ylen exceeds 64");

   long xl = parseAsLong(x);
   long yl = parseAsLong(y);
   return xl + yl;
}

private long parseAsLong(String s) 
{
   long l = 0L;
   for(int i = 0; i < s.length; i++) {
      Char c = s.getAt(i);
      if(c == '0') 
         continue;
      else if(c == '1')
         l |= (1L << i);
      else 
         throw new IllegalArgumentException("Invalid character at index" + i);     
   }
   return l;
}

public long sum(String x, String y)
{
   if(x == null || y == null)
      throw new IllegalArgumentException("X or/and y is null");
   if(x.length > 64 || y.length > 64)
      throw new IllegalArgumentException("xlen, ylen exceeds 64");

   long xl = parseAsLong(x);
   long yl = parseAsLong(y);
   return xl + yl;
}

private long parseAsLong(String s) 
{
   long l = 0L;
   for(int i = 0; i < s.length; i++) {
      Char c = s.getAt(i);
      if(c == '0') 
         continue;
      else if(c == '1')
         l |= (1L << i);
      else 
         throw new IllegalArgumentException("Invalid character at index" + i);     
   }
   return l;
}

public long sum(String x, String y)
{
   if(x == null || y == null)
      throw new IllegalArgumentException("X or/and y is null");
   if(x.length > 64 || y.length > 64)
      throw new IllegalArgumentException("xlen, ylen exceeds 64");

   long xl = parseAsLong(x);
   long yl = parseAsLong(y);
   return xl + yl;
}

private long parseAsLong(String s) 
{
   long l = 0L;
   for(int i = 0; i < s.length; i++) {
      Char c = s.getAt(i);
      if(c == '0') 
         continue;
      else if(c == '1')
         l |= (1L << i);
      else 
         throw new IllegalArgumentException("Invalid character at index" + i);     
   }
   return l;
}

public static long sum(String x, String y)
   {
      if(x == null || y == null)
         throw new IllegalArgumentException("X or/and y is null");
      if(x.length() > 64 || y.length() > 64)
         throw new IllegalArgumentException("xlen, ylen exceeds 64");

      long xl = parseAsLong(x);
      System.out.println(xl);
      long yl = parseAsLong(y);
      System.out.println(yl);

      return xl + yl;
   }

   private static long parseAsLong(String s) 
   {
      long l = 0L;
      int n = s.length();
      for(int i = 0; i < n; i++) {
         char c = s.charAt(i);
         if(c == '0') 
            continue;
         else if(c == '1')
            l |= (1L << (n - i - 1));
         else 
            throw new IllegalArgumentException("Invalid character at index" + i);     
      }
      return l;
   }

public static String add(String str1, String str2) {

		int i = str1.length() - 1;
		int j = str2.length() - 1;
		boolean rem = false;
		StringBuilder builder = new StringBuilder();

		while (i >= 0 && j >= 0) {

			char a = str1.charAt(i--);
			char b = str2.charAt(j--);

			if (a == '1' && b == '1') {

				if (rem) {
					builder.append('1');
				} else {
					builder.append('0');
				}
				rem = true;

			} else if (a == '0' && b == '0') {
				if (rem) {
					builder.append('1');
				} else {
					builder.append('0');
				}
				rem = false;

			} else {

				if (rem) {
					builder.append('0');
				} else {
					builder.append('1');
				}
			}
		}

		int c = i > j ? i : j;
		String strRem = i > j ? str1 : str2;

		while (c >= 0) {
			char a = strRem.charAt(c--);
			if (a == '0' && rem) {
				builder.append('1');
				rem = false;
			} else if (a == '1' && rem) {
				builder.append('0');
			} else {
				builder.append(a);
			}
		}
		if (rem)
			builder.append('1');
		return builder.reverse().toString();
	}

public void addBinaries(String inputString1, String inputString2){
		int len1 = inputString1.length();
		int len2 = inputString2.length();
		StringBuffer sb1 = new StringBuffer(inputString1).reverse();
		StringBuffer sb2 = new StringBuffer(inputString2).reverse();
		StringBuffer sb3 = new StringBuffer();
		
		if(len1 > len2){
			padZero(sb2, len1);
		}else{
			padZero(sb1, len2);
		}
		int carry = 0;
		
		for (int i = 0; i < sb1.length(); i++) {
			int sum = carry + Integer.valueOf(String.valueOf(sb1.charAt(i))) + Integer.valueOf(String.valueOf(sb2.charAt(i)));
			if(sum == 0){
				sb3.append(sum);
			}else if(sum > 0 && sum % 2 == 0){
				sb3.append(0);
				carry = 1;
			}else if(sum == 1){
				sb3.append(1);
			}else if(sum > 0 && sum > 2){
				sb3.append(1);
				carry = 1;
			}
		}
		
		if(carry == 1){
			sb3.append(1);
		}
		
		System.out.println(sb3.reverse());	
	}


	private void padZero(StringBuffer sb, int len) {
		while(sb.length()!=len){
			sb.append(0);
		}	
	}

before return statement :
if (carry > 0 ) {
sb.insert(0,'1');
}

#include<stdio.h>
#include<string.h>
int main()
{
char s1[]="01011111";
char s2[]="11000";
char s3[20],carry='0';
int c1=0,c2=0,i,j,k=0;
c1=sizeof(s1)/sizeof(s1[0]);
c2=sizeof(s2)/sizeof(s2[0]);
i=c1;
j=c2;
while(i>=0&&j>=0)
{
if(s1[i]==s2[j])
{
if(s1[i]=='1')
{
if(carry=='0')
{
s3[k]='0';
}
else
s3[k]='1';
carry='1';
}
else
{
if(carry=='0')
s3[k]='0';
else
{
s3[k]='1';
}
carry='0';
}
}
else
{
if(carry=='0')
{
s3[k]='1';
carry='0';
}
else
{
s3[k]='0';
carry='1';
}
}
k++;
j--;
i--;
}

if(i>=0)
{
while(i>=0)
{
if(s1[i]=='0')
{
if(carry=='1')
s3[k]='1';
else
s3[k]='0';
carry='0';
}
else
{
if(carry=='1')
{
s3[k]='0';
carry='1';
}
else
{
s3[k]='1';
carry='0';
}
}
i--;
k++;
}
}
else
{
while(j>=0)
{
if(s2[j]=='0')
{
if(carry=='1')
s3[k]='1';
else
s3[k]='0';
}
else
{
if(carry=='1')
{
s3[k]='0';
carry='1';
}
else
s3[k]='1';
}
j--;
k++;
}
}
k--;

while(k>1)
{
printf("%c",s3[k]);
k--;
}

return 0;
}
Time complexity:O(n)
where 'n' is length of bigger string