Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 2 vote

Theory

sum = a xor b xor c
carry = ab + bc+ ac

Code

int addBinary(int a1[], int a2[], int result[]){
    int i, c = 0;
    for(i = 0; i < 8 ; i++){
        result[i] = ((a1[i] ^ a2[i]) ^ c); //a xor b xor c
        c = ((a1[i] & a2[i]) | (a1[i] &c)) | (a2[i] & c); //ab+bc+ca
    }
    result[i] = c;
    return c;
 }

- Saurabh2816 December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] add( int[] a, int[] b ){
	int len = a.length + 1;
	int[] newa = a;
	int[] newb = b;
	if( a.length < b.length ){
		len = b.length + 1;
		newa = new int[b.length];
		for( int i = a.length; i < b.length; i ++ )
			newa[ i ] = 0;
	} else {
		len = a.length + 1;
		newb = new int[a.length];
		for( int i = b.length; i < a.length; i ++ )
			newb[ i ] = 0;
	}
	int t = 0;
	for( int i = len - 1; i > 0; i -- ){
		ret[ i ] = ( newa[i-1] + newb[i-1] + t ) % 2;
		t = newa[i-1] + newb[i-1] > 1 ? 1 : 0;
	}
	ret[ 0 ] =t;
	return ret;
}

- chandler.c.zuo December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. add "0" to the MSB of the two strings so that their lengths match
2. iterate on the two strings one bit at a time starting with LSB and do bitwise addition and accumulate result
3. reverse the result

## INPUT STRING
str1 = "100011"
str2 = "100100"

## bit stuff the strings with "0" in MSB location
maxlen = max(len(str1), len(str2))
bitStuffedString1 = "0"*(len(str1)-maxlen) + str1
bitStuffedString2 = "0"*(len(str2)-maxlen) + str2

## bitwise add starting from LSB
cin = 0
result = ""
for (x, y) in zip(reversed(bitStuffedString1), reversed(bitStuffedString2)):
    bitAddRes = int(x) + int(y) + cin
    result += str(bitAddRes % 2)
    cin = bitAddRes/2
result += str(cin)

## reverse the result so LSB is at the max index
result = result[::-1]
print result

- whatevva' December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Am I wrong in assuming what they want you to *bitwise OR* both numbers

0b100011 | 0b100100 = 0b1000111

- gagomes December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

6b'100011 | 6b'100100 != 7b'1000111

6b'100011 | 6b'100100 ==  6b'100111

- whatevva' December 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int binaryToInt(string binaryString)
{
	int convertedInt = 0;
	for (int i = binaryString.length; i > 0; i-- )
	{
		convertedInt += binaryString.charAt(i) == "1" ? 2^(binaryString.length - i) : 0;
	}
	return convertedInt;
}

public string binaryAddition(string one, string two)
{
	string binarySum = "";
	var sum = binaryToInt(one) + binaryToInt(two);
	while (sum > 0)
	{
		binarySum += sum % 2;
		sum = sum / 2;
	}
	return binarySum;
}

- echen57 December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just add from right to left. C++ version:

string sumBinary(const string& a, const string& b)
{
    string c;
    c.reserve(a.size() > b.size() ? a.size() : b.size());

    //add from right to left
    int i = a.size()-1, j = b.size()-1, co = 0;
    for(; i >= 0 && j >= 0; --i, --j){
        if((a[i]-'0') ^ (b[i]-'0') ^ co) c.push_back('1');
        else c.push_back('0');
        if((a[i]-'0') + (b[i]-'0') + co > 1) co = 1;
        else co = 0;
    }
    
    //add up the remaining
    const string* p = i >= 0 ? &a : &b;
    const string& t = *p;
    int k = i >= 0 ? i : j;
    for(; k >= 0; --k){
        if((t[i]-'0') ^ co) c.push_back('1');
        else c.push_back('0');
        if((t[i]-'0') + co > 1) co = 1;
        else co = 0;
    }
    if(co) c.push_back('1');
    
    //reverse the string
    for(i = 0, j = c.size()-1; i < j; ++i, --j){
        char ch = c[i];
        c[i] = c[j];
        c[j] = ch;
    }
    
    return c;
}

- Anonymous December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In c:
{
int sumTwoBinaryNumbers(int a, int b) {
int firstNumber = 0;

for (int i = 0; a > 0; i++) {
int remainder = a % 10;

firstNumber += (remainder * pow(2, i));
a /= 10;
}

int secondNumber = 0;

for (int i = 0; b > 0; i++) {
int remainder = b % 10;

secondNumber += (remainder * pow(2, i));
b /= 10;
}

return firstNumber + secondNumber;
}}

- Nick December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Wow this one looks easy but still took me a while. I am taking the standard approach of adding up the digits one by one (starting from the end of the strings).

static String sum(String s, String s2) {
    if(s.length() >= s2.length())
      return sumHelper(s, s2);
    else return sumHelper(s2, s);
  }

  static String sumHelper(String longer, String shorter) {
    StringBuilder sb = new StringBuilder();
    int carry = 0;
    int longerLen = longer.length();
    int shorterLen = shorter.length();
    for(int i=0; i<shorterLen; i++) {
      int longerDigit = longer.charAt(longerLen - 1 - i) - '0';
      int shorterDigit = shorter.charAt(shorterLen - 1 - i) - '0';
      int digit = longerDigit + shorterDigit + carry;
      sb.insert(0, (digit % 2 == 0 ? '0' : '1'));
      carry = digit/2;
    }
    for(int i=longerLen-shorterLen-1; i>=0; i--) {
      int longerDigit = longer.charAt(i);
      int digit = longerDigit + carry;
      sb.insert(0, (digit % 2 == 0 ? '0' : '1'));
      carry = 0;
    }
    if(carry > 0)
      sb.insert(0, '1');
    return sb.toString();
  }

- Sunny December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1:
Iterate through the bits in larger binary number and perform bitwise addition
with smaller binary number with carry forward.
Step 2:
Add the result in a list and reverse the final result and store it in result array

private static int[] addBinary(int[] a, int b[]) {
		List<Integer> l = new ArrayList<Integer>();

		int max = Math.max(a.length, b.length);
		int c = 0;
		for (int i = max - 1; i >= 0; i--) {
			int x = a.length - max + i >= 0 ? a[a.length - max + i] : 0;
			int y = b.length - max + i >= 0 ? b[b.length - max + i] : 0;

			if (x != y || x != 1) {
				int r = (x | y) ^ c;
				l.add(r);
				c = c == 1 ? (r ^ 1) : 0;
			} else {
				l.add(1 & c);
				c = 1;
			}

		}
		if (c > 0) {
			l.add(c);
		}
		int[] result = new int[l.size()];
		int k = 0;
		for (int i = l.size() - 1; i >= 0; i--) {
			result[k++] = l.get(i);
		}
		return result;
	}

- ganni December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well, it seem that the question is really about bitwise operations. The following code was intentionally left unoptimized in variables use just to preserve logic simplicity.

def bwsum(a, b):
	sum = a
	rem = b

	while rem:
		acc = sum
		sum = acc ^ rem
		rem = (acc & rem) << 1

	return sum

print(bwsum(123, 456))

- Mishka December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good one

- Sachin March 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Really nice solution ....

- newlearner February 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

string addBitStrings( string first, string second )
{
string result; // To store the sum bits

// make the lengths same before adding
int length = makeEqualLength(first, second);
int carry = 0; // Initialize carry

// Add all bits one by one
for (int i = length-1 ; i >= 0 ; i--)
{
int firstBit = first.at(i) - '0';
int secondBit = second.at(i) - '0';

// boolean expression for sum of 3 bits
int sum = (firstBit ^ secondBit ^ carry)+'0';

result = (char)sum + result;

// boolean expression for 3-bit addition
carry = (firstBit&secondBit) | (secondBit&carry) | (firstBit&carry);
}

// if overflow, then add a leading 1
if (carry) result = '1' + result;

return result;
}


//source geeksforgeeks

- alex December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>
#define MIN(x,y) ((x) < (y))?(x):(y)
#define MAX(x,y) ((x) > (y))?(x):(y)
#define SAFE_STRLEN(x) ((x)?strlen(x):0)

//Returns dynamically allocated string needs to be freed                                                                                                                                                                                                                      
char * addNums(char*num1,char * num2)
{

  int lenOfSum = MAX(SAFE_STRLEN(num1),SAFE_STRLEN(num2)) + 2;
  int lenOfCommonParts = MIN(strlen(num1?num1:""),strlen(num2?num2:""));

  char * num = new char[lenOfSum];
  int i;

  memset(num,0,lenOfSum);

  bool digit1, digit2,carry = false;

  for(int i = 0; i < lenOfCommonParts; i++)
  {
    digit1 = num1[strlen(num1?num1:"") - i -1] == '1';
    digit2 = num2[strlen(num2?num2:"") - i -1] == '1';

    num[i] = ((digit1 ^ digit2) ^ carry)?'1':'0';
    carry = ((int)digit1 + (int)digit2 + (int)carry) > 1;

  }
  char * leftOver = strlen(num1?num1:"") > strlen(num2?num2:"") ? num1 : num2;

  for(int i = lenOfCommonParts; i < SAFE_STRLEN(leftOver); i++)
    {
      digit1 = leftOver[strlen(leftOver) - i -1] == '1';
      num[i] = (digit1  ^ carry)?'1':'0';
      carry = ((int)digit1  + (int)carry) > 1;
    }

    if(carry)
      num[strlen(num)] = '1';

    int length = strlen(num);
    puts(num);
    for(int i = 0; i < length/2; ++i)
      {
        char dig = num[i];
        num[i] = num[length - i - 1];
        num[length -i-1] = dig;
      }
  return num;

}

- Anonymous December 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python implementation:

def find_sum(a, b, base=2):
    a_str, b_str = str(a), str(b)

    if len(a_str) < len(b_str):
        a_str = '0' * (len(b_str) - len(a_str)) + a_str
    else:
        b_str = '0' * (len(a_str) - len(b_str)) + b_str

    result = []
    counter = len(a_str) - 1
    reminder = 0
    while counter > -1:
        current = int(a_str[counter]) + int(b_str[counter]) + reminder

        if current >= base:
            result.append(current % base)
            reminder = 1
        else:
            result.append(current)
            reminder = 0

        counter -= 1

    if reminder:
        result.append(reminder)

    return ''.join(map(str, reversed(result)))

- vasyl.stanislavchuk December 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#Ruby 2.0.0 implementation

input_1 = "100011".reverse
input_2 = "100100".reverse
output = []

# value added carry on
carry = 0

# get the longest number to add
if input_1.size >= input_2.size
  long_input = input_1
  short_input = input_2
else
  long_input = input_2
  short_input = input_1
end

# for each number
long_input.each_char.with_index do |number, index|
  # Adds
  sum = (number.to_i + short_input[index].to_i + carry)

  # If additon overflows
  if sum > 1
    # We only add the mod of the value
    output << sum % 2
    # Carry the number of overflows
    carry = sum/2
  else
    # easy add without an overflow
    output << sum
    carry = 0
  end
end

# Captures the final overflow
unless carry == 0
  output << carry
end

# Put it out
output.reverse.join

- JĂșlio Bueno December 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max(a,b) ((a) > (b))?(a):(b)

void SomaBinario(char *b1, char *b2, char *result) {
int l1, l2, carrie = 0, i;
l1 = strlen(b1)-1;
l2 = strlen(b2)-1;
i = max(l1,l2) + 3;
result = (char*)malloc((i)*sizeof(char));
result[--i] = '\0';
i--;

while ((l1 >= 0) && (l2 >= 0)){
int n1 = b1[l1] - '0';
int n2 = b2[l2] - '0';
int soma;
soma = n1 + n2 + carrie;

carrie = (soma > 1)?1:0;

result[i] = (soma%2) + '0';

i--;
l1--;
l2--;
}

if (l1 > l2) {

while (l1 >= 0){
int n1 = b1[l1] - '0';
int soma;
soma = n1 + carrie;

carrie = (soma > 1)?1:0;

result[i] = (soma%2) + '0';

i--;
l1--;
}

} else {
while (l2 >= 0){
int n2 = b2[l2] - '0';
int soma;
soma = n2 + carrie;

carrie = (soma > 1)?1:0;

result[i] = (soma%2) + '0';

i--;
l2--;
}

}
if (carrie)
result[i] = carrie + '0';

printf("%s", result);

}


int main(){
char bin1[] = "101111", bin2[] = "1110101", *resultado;

SomaBinario(bin1, bin2, resultado);
return 0;

}

- Anonymous December 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max(a,b) ((a) > (b))?(a):(b)

void sum(char *b1, char *b2, char *result) {
	int l1, l2, carrie = 0, i;
	l1 = strlen(b1)-1;
	l2 = strlen(b2)-1;
	i = max(l1,l2) + 3;
	result = (char*)malloc((i)*sizeof(char));
	result[--i] = '\0';
	i--;
	
	while ((l1 >= 0) && (l2 >= 0)){
		int n1 = b1[l1] - '0';
		int n2 = b2[l2] - '0';
		int soma;
		soma = n1 + n2 + carrie;
		
		carrie = (soma > 1)?1:0;
		
		result[i] = (soma%2) + '0';		
				
		i--;
		l1--;
		l2--;
	}
			
	if (l1 > l2) {
	
		while (l1 >= 0){
			int n1 = b1[l1] - '0';
			int soma;
			soma = n1 + carrie;
			
			carrie = (soma > 1)?1:0;
			
			result[i] = (soma%2) + '0';		
						
			i--;
			l1--;
		}
		
	} else {
		while (l2 >= 0){
			int n2 = b2[l2] - '0';
			int soma;
			soma = n2 + carrie;
			
			carrie = (soma > 1)?1:0;
			
			result[i] = (soma%2) + '0';	
			printf("[%c]", result[i]);
						
			i--;
			l2--;
		}
		
	} 
	if (carrie)
			result[i] = carrie + '0';
	
	printf("%s", result);
		
}


int main(){
	char bin1[] = "101111", bin2[] = "1110101", *resul;
	
	Sum(bin1, bin2, result);
	return 0;

}

- Anonymous December 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Java:

public static String addBinary(String val1, String val2) {
		int maxLength = val1.length() >= val2.length() ? val1.length() : val2.length();
		int previousCarry = 0;
		String sumStr = "";
		int i = 1;
		while(i <= maxLength) {
			int result = 0;
			char fc = i > val1.length() ? '0' : val1.charAt(val1.length() - i);
			char sc = i > val2.length() ? '0' : val2.charAt(val2.length() - i);
			if(fc == '0' && sc == '0' && previousCarry == 0) {
				previousCarry = 0;
				result = 0;
			}
			else if(fc == '0' && sc == '0' && previousCarry == 1) {
				previousCarry = 0;
				result = 1;
			}
			else if(fc == '0' && sc == '1' && previousCarry == 0) {
				previousCarry = 0;
				result = 1;
			}
			else if(fc == '0' && sc == '1' && previousCarry == 1) {
				previousCarry = 1;
				result = 0;
			}
			else if(fc == '1' && sc == '0' && previousCarry == 0) {
				previousCarry = 0;
				result = 1;
			}
			else if(fc == '1' && sc == '0' && previousCarry == 1) {
				previousCarry = 1;
				result = 0;
			}
			else if(fc == '1' && sc == '1' && previousCarry == 0) {
				previousCarry = 1;
				result = 0;
			}
			else if(fc == '1' && sc == '1' && previousCarry == 1) {
				previousCarry = 1;
				result = 1;
			}
			else {
				throw new RuntimeException("Invalid binary numbers.");
			}
			sumStr = result + sumStr;
			i++;
		}
		sumStr = previousCarry + sumStr;
		return sumStr;
	}

- Anonymous December 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class BitwiseOperation {
	public static String sumOfBinaryNumbers(String a,String b)
	{
		a=a.replace(" ", "");
		b=b.replace(" ", "");
	    char n[]=a.toCharArray();
		char m[]=b.toCharArray();
		StringBuffer result=new StringBuffer();
		int carry=0;
		int i=n.length-1,j=m.length-1;
		while(i>=0 && j>=0)
		{
		 int r1=Integer.parseInt(n[i]+"");
		 int r2=Integer.parseInt(m[j]+"");
		 int value=(r1^r2^carry);
		 carry=((r1 & r2) | (r1 &carry)) | (r2 & carry); 
		 result.append(value);
		 i--;
		 j--;
		}
		while(i>=0)
		   {
			int value=Integer.parseInt(n[i]+"")^carry;
			if(value==1)
				carry=0;
			else
				carry=1;
			result.append(value);
			i--;
		   }
		while(j>=0)
		{
			int value=Integer.parseInt(m[j]+"")^carry;
			if(value==1)
				carry=0;
			else
				carry=1;
			result.append(value);
			j--;
		}
		if(carry==1)
		result.append(carry);
		result.reverse();
	  return result.toString();
	}
	public static void main(String[] args)
	{
	 String result= sumOfBinaryNumbers("100011","100100");
	 System.out.println("Result "+result);
	}
}

- niks December 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

std::string Add(std::string & str1, std::string & str2) {
int m = str1.size();
int n = str2.size();
int i = m - 1;
int j = n - 1;
int c = 0;
std::string rs(std::max(m, n), '0');
int k = rs.size() - 1;
while (i >= 0 || j >= 0 || c >0) {
int t = c;
if (i >= 0) t += str1[i--] - '0';
if (j >= 0) t += str2[j--] - '0';
c = t / 2;
t = t % 2;
if (k >= 0) rs[k--] = t + '0';
else rs.insert(rs.begin(), t + '0');
}
return rs;
}

- guoliqiang2006 December 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java :

static void printBinarySum(String n1, String n2) {
		
		// Set the strings to the same length
		
		int gap = n1.length() - n2.length();
		char[] zeros = new char[Math.abs(gap)];
		Arrays.fill(zeros, '0');
		String zeros_string = new String(zeros);
		String big_string, small_string;
		if(gap >= 0) {
			big_string = n1;
			small_string = zeros_string + n2;
		}
		else {
			big_string = n2;
			small_string = zeros_string + n1;
		}
		
		// Do the sum
		
		boolean carry = false;
		boolean[] result = new boolean[big_string.length()];
		
		for(int i = big_string.length() - 1; i != -1; i--) {
			boolean bit1 = big_string.charAt(i) == '1';
			boolean bit2 = small_string.charAt(i) == '1';
			result[i] = bit1 ^ bit2 ^ carry;
			carry = (bit1 && bit2) || (bit2 && carry) || (carry && bit1);
		}
		if(carry)
			System.out.print("1");
		for(int i = 0; i != result.length; i++)
			System.out.print(result[i] ? "1" : "0");
	}

- cinderton December 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my code in Objective-C

- (NSArray *)sumUpNumberArray:(NSArray *)numbA withNumberArray:(NSArray *)numbB {
    NSInteger maxCount = MAX([numbA count], [numbB count]);
    NSMutableArray *rtMArray = [NSMutableArray arrayWithCapacity:maxCount];
    NSInteger gapNumbA = maxCount-[numbA count];
    NSInteger gapNumbB = maxCount-[numbB count];
    NSInteger addSum = 0;
    NSInteger iterator = maxCount;
    while ((iterator - gapNumbA - 1 >= 0) && (iterator - gapNumbB - 1 >= 0)) {
        addSum += [numbA[iterator - gapNumbA - 1] integerValue] + [numbB[iterator - gapNumbB - 1] integerValue];
        [rtMArray insertObject:@(addSum%2) atIndex:0];
        --iterator;
        addSum /= 2;
    }
    
    // if numbA has more
    while (iterator - gapNumbA - 1 >= 0) {
        addSum += [numbA[iterator - gapNumbA - 1] integerValue];
        [rtMArray insertObject:@(addSum%2) atIndex:0];
        --iterator;
        addSum /= 2;
    }
    
    // if numbB has more
    while (iterator - gapNumbB - 1 >= 0) {
        addSum += [numbA[iterator - gapNumbB - 1] integerValue];
        [rtMArray insertObject:@(addSum%2) atIndex:0];
        --iterator;
        addSum /= 2;
    }
    
    if (addSum > 0) {
        [rtMArray insertObject:@(addSum%2) atIndex:0];
    }
    return rtMArray;
}

// Test:
NSArray *array = [self sumUpNumberArray:@[@1, @0, @0, @0, @1, @1] withNumberArray:@[@1, @0, @0, @1, @0, @0]];

- Senry December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

This is a nice question as any basic addition for a n&m n>m bit
there will be n XORs, n AND and carry management
this can be reduced based on the number of 1's in the numbers
let the numbers be a&b;

while(a!=0)
{
c = a XOR b;
a = (a&b)<1;
}

- annnnn December 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution with tail recursion:

- (int) add:(int)A to:(int)B withRetenue:(int)retenue{
	int currentNumberA = A%10;
	int currentNumberB = B%10;
	int result = 0;
	
	int tempResult = currentNumberA + currentNumberB + retenue;
	
	result = tempResult%2;
	return result + ((A/10 + B/10) == 0 ? 0 :[self add:A/10 to:B/10 withRetenue:tempResult/2]*10);

}

- Florent Crivello January 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oops, here it is:

- (int) add:(int)A to:(int)B withDeduction:(int)deduction index:(int)index{
	int currentNumberA = A%10;
	int currentNumberB = B%10;
	int result = 0;
	
	int sum = currentNumberA + currentNumberB + deduction;
	int nextDeduction = sum / 2;
	
	result = (sum % 2) * (pow(10, index));
	
	if(A/10+B/10+nextDeduction == 0){
		return result;
	}
	
	return result + [self add:A/10 to:B/10 withDeduction:nextDeduction index:index+1];
}

- Florent Crivello January 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A Java impl with the main driver. Takes the binary numbers as args.

public class BinaryAddition {

    /* Driver */
    public static void main(String[] args) {

        if (!(args.length == 2))
            System.exit(-1);

        int diff = Math.abs(args[0].length() - args[1].length());

        if (args[0].length() > args[1].length()) {
            args[1] = balance(args[1], diff);
        } else {
            args[1] = balance(args[1], diff);
        }
        System.out.println(args[0]);
        System.out.println(args[1]);
            
        int[] a = new int[args[0].length()];
        int[] b = new int[args[1].length()];

        for (int i=0; i<a.length; i++)
            a[i] = args[0].charAt(i)-'0';

        for (int i=0; i<b.length; i++)
            b[i] = args[1].charAt(i)-'0';

        int[] res = binaryAdd(a, b);

        // Test case
        StringBuilder sb = new StringBuilder();
        for (int i=0; i< res.length; i++)
            sb.append(res[i]);
        
        System.out.println("Result: "+ sb);
    }

    private static int[] binaryAdd(int[] a, int[] b) {
        int[] result = new int[a.length+1];
        int c=0;
        for (int i = a.length-1; i >= 0 ; i--) {
            result[i+1] = a[i] ^ b[i] ^ c;
            c= a[i]*b[i] + b[i]*c + c*a[i];
            c = c%2;
        }
        result[0] = c;
        return result;
    }

    private static String balance(String ip, int diff) {
        if (diff==0)
            return ip;
        StringBuilder sb = new StringBuilder();
        while(diff > 0) {
            sb.append('0');
            diff--;
        }
        sb.append(ip);
        return sb.toString();
    }
}

- Shishir January 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Sum binary numbers
void sum_binary(int num1[], int num2[], short size)
{
	int *result = new int[size + 1];
	int carry = 0;
	for (short i = size; i > 0; --i)
	{
		result[i] = num1[i-1] ^ num2[i-1] ^ carry;
		carry = (num1[i-1] && num2[i-1]) || (carry && (num1[i-1] || num2[i-1]));
	}
	result[0] = carry;
	
	cout << " ";
	for (auto x = 0; x < size; ++x)
		cout << num1[x];
	cout << endl << " ";
	for (auto x = 0; x < size; ++x)
		cout << num2[x];
	cout << endl;
	for (auto x = 0; x < size + 1; ++x)
		cout << result[x];
	cout << endl;
	
	delete [] result;

}

- Bhuvan February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
char a[8] = "00100011";
char b[8] = "00100100";
char c[8] = {0};
int i = 7;
//i = strlen(a)-1;
for(i = 7;i>=0;i--)
{
c[i] = a[i] +b[i] - '0';
if(c[i] > '1'){
c[i] = '0';
a[i-1] = '1';
}

//printf("%c", c[i]);
}
for(i=0;i<8;i++)
printf("%c",c[i]);
}

- chindee February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

seems to work...thanks !

- kejnik February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

preserved formatting

int main() 
{ 
char a[8] = "00100011"; 
char b[8] = "00100100"; 
char c[8] = {0}; 
int i = 7; 
//i = strlen(a)-1; 
for(i = 7;i>=0;i--) 
{ 
c[i] = a[i] +b[i] - '0'; 
if(c[i] > '1'){ 
c[i] = '0'; 
a[i-1] = '1'; 
} 

//printf("%c", c[i]); 
} 
for(i=0;i<8;i++) 
printf("%c",c[i]); 
}

- chindee... February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is JavaScript implementation. Can you explain what they actually test here?
Writing binary number string to number converter?
Imitating bit-wise operations?
What?

(parseInt("100011", 2) + parseInt("100100", 2)).toString(2);

- Andrey Yeliseyev February 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

parseInt takes a number and a base and converts it to base 10.

so

parseInt("100011", 2)

is 35 and

parseInt("100100", 2)

is 36.

String.prototype.toString takes an argument (number) as a base, and returns the number converted to the inputted base.

Basically, this code converts binary to decimal, sums, then converts back to binary

- Amar August 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void foo(const char *s1, const char *s2)
{
    int l1, l2, l;
    char *s;

    if (s1 == NULL || s2 == NULL || s1[0] == '\0' || s2[0] == '\0') return;

    l1 = strlen(s1);
    l2 = strlen(s2);

    if (l1 < l2) {
        l = l2 + 1;
    } else {
        l = l1 + 1;
    }

    s = (char *)malloc(l + 1);
    if (s == NULL) return;
    s[l] = '\0';

    l1--;
    l2--;
    l--;

    int sum, carry = 0;

    while (l1 >= 0 && l2 >= 0) {
        //printf("carry: %d\n", carry);

        sum = s1[l1] - '0' + s2[l2] - '0' + carry;

        //printf("sum: %d\n", sum);

        if (sum > 1) {
            sum -= 2;
            carry = 1;
        } else {
            carry = 0;
        }

        s[l--] = (char)(sum + '0');

        l1--;
        l2--;
    }

    while (l1 >= 0) {
        sum = s1[l1] - '0' + carry;

        if (sum > 1) {
            sum -= 2;
            carry = 1;
        } else {
            carry = 0;
        }

        s[l--] = (char)(sum + '0');

        l1--;
    }

    while (l2 >= 0) {
        sum = s2[l2] - '0' + carry;

        if (sum > 1) {
            sum -= 2;
            carry = 1;
        } else {
            carry = 0;
        }

        s[l--] = (char)(sum + '0');

        l2--;
    }

    if (l >= 0) {
        if (carry > 0) s[l--] = '1';
        else while (l >= 0) s[l--] = '0';
    }

    printf("s1: %s\ns2: %s\nsum: %s\n", s1, s2, s);

    free(s);
}

- Microwish February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int sumOfBinaryNumber()
{
long binary1, binary2;
int i = 0, remainder = 0, sum[20];

printf("Enter the first binary number: ");
cin>>binary1;
printf("Enter the second binary number: ");
cin>>binary2;
while (binary1 != 0 || binary2 != 0)
{
sum[i++] =(binary1 % 10 + binary2 % 10 + remainder) % 2;
remainder =(binary1 % 10 + binary2 % 10 + remainder) / 2;
binary1 = binary1 / 10;
binary2 = binary2 / 10;
}
if (remainder != 0)
sum[i++] = remainder;
--i;
printf("Sum of two binary numbers: ");
while (i >= 0)
printf("%d", sum[i--]);
return 0;
}

- Abhijeet Kandalkar March 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

NSString * sumBinaryNumbers (NSString *b1, NSString *b2) {
    
    int counter = [b1 length];
    if ([b1 length] > [b2 length]) {
        int lenDiff = [b1 length] - [b2 length];
        NSString *zeros = [@"" stringByPaddingToLength:lenDiff * [@"0" length] withString:@"0" startingAtIndex:0];
        b2 = [zeros stringByAppendingString:b2];
    } else {
        int lenDiff = [b2 length] - [b1 length];
        NSString *zeros = [@"" stringByPaddingToLength:lenDiff * [@"0" length] withString:@"0" startingAtIndex:0];
        b1 = [zeros stringByAppendingString:b1];
    }
    
    NSMutableString *result = [NSMutableString new];
    NSString *one = [NSMutableString stringWithString:@"1"];
    NSString *zero = [NSMutableString stringWithString:@"0"];
    int carry = 0;
    
    for (int i=counter-1; i>=0; i--) {
        if ([b1 characterAtIndex:i] == '0' && [b2 characterAtIndex:i] == '0') {
            if (carry == 0) {
                result = [NSMutableString stringWithFormat:@"%@%@", result, zero];
            } else {
                result = [NSMutableString stringWithFormat:@"%@%@", result, one];
            }
        } else if ([b1 characterAtIndex:i] == '0' && [b2 characterAtIndex:i] == '1') {
            if (carry == 0) {
                result = [NSMutableString stringWithFormat:@"%@%@", result, one];
                carry = 0;
            } else {
                result = [NSMutableString stringWithFormat:@"%@%@", result, zero];
                carry = 1;
            }
        } else if ([b1 characterAtIndex:i] == '1' && [b2 characterAtIndex:i] == '0') {
            if (carry == 0) {
                result = [NSMutableString stringWithFormat:@"%@%@", result, one];
                carry = 0;
            } else {
                result = [NSMutableString stringWithFormat:@"%@%@", result, zero];
                carry = 1;
            }
        } else {
            if (carry == 0) {
                result = [NSMutableString stringWithFormat:@"%@%@", result, zero];
            } else {
                result = [NSMutableString stringWithFormat:@"%@%@", result, one];
            }
            carry = 1;
        }
    }
    
    if (carry == 1) {
        result = [NSMutableString stringWithFormat:@"%@%@", one, result];
    }
    
    return result;
}

- peeterparker April 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>

int main() {

unsigned int arr[8] = {1,1,0,0,1,0,0,1}, arr1[8]={0,1,1,0,1,1,0,1};
int carry=0;

unsigned int sum[8];
int i;

for(i=7; i>=0; i--) {

sum[i] = (arr[i] ^ arr1[i]) ^ carry;
if ((arr[i] && carry) || (arr1[i] && carry) || (arr1[i] && arr[i]))
carry = 1;
else
carry = 0;

}

//Display the sum result

for(i=0 ; i <8 ;i++){

printf("%d", sum[i]);
}

printf("\nCarry : %d", carry);
}
~

- Audya April 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int Add(int x, int y)
{
    if (y == 0)
        return x;
    else
        return Add( x ^ y, (x & y) << 1);
}

- Learn June 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a = 100010,b = 100100;
int c = a & b;
int d = a^b;
while(c){
c = c << 1;
d = d^c;
c = c & d;
}

- shubham7stark August 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

main()
{
int a = 1725; // example value
int b = 1357; // example value
int andr = 0;
int orr = 0;
int i = 1;
int m = 0;

andr = (a & b);

orr = (a | b);

while(i != 0)
{
if(andr & i)
{
m = i;
while(m & orr)
{
orr &= ~m;
m <<= 1;
}
orr |= m;
m = 0;
}
i <<= 1;
}

printf("sum is %i \n",orr);

}

- Siddarth October 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> sumBitwise(vector<int> a, vector<int> b){
	vector<int> sum;
	// set sum to 0:
	for(size_t i=0; i<a.size(); i++) sum.push_back(0);

	sumBitwise(a, b, a.size()-1, 0, sum); // start with 0 carry and at the rightmost position.

	return sum;	
}

void sumBitwise(vector<int>& a, vector<int>& b, int sumPosition, int carry, vector<int>& sumSoFar){
	// base case:
	if(sumPosition < 0) break;
	
	sumOfPosition = a[sumPosition] + b[sumPosition]  + carry; // can't have a carry > 1
	if(sumOfPosition > 1)
	{
		sumSoFar[sumPosition] = 1;
		sumBitwise(a, b, sumPosition - 1, 1, sumSoFar); // recurse with carry
	}
	else
	{
		sumSoFar[sumPosition] = sumofPosition;
		sumBitwise(a, b, sumPosition - 1, 0, sumSoFar); // recurse w/o carry
	}
}

- Anonymous April 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

XOR, AND and OR bitwise can solve. Assuming both arrays sent are of same length (we can add more code based on whichever is max length and XOR with 0 if min length). This would print (return array) of bits.

public int[] bitAddition(int[] num1, int[] num2) {
		int sum[] = new int[num1.length + 1];
		int i = 0, carry =0;
		for ( i = num1.length-1; i >= 0; i--) {
			sum[i+1] = num1[i] ^ num2[i] ^ carry;
			carry = (num1[i] & num2[i]) | (num1[i] & carry) | (num2[i] & carry);
		}
		sum[0] = carry;
		return sum;
	}

- v32 February 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 4 vote

In Java:

public String (String num1, String num2) {
  // Use as radix 2 to convert binary num   
  return Integer.toBinaryString(Integer.parseInt(num1, 2)+ Integer.parseInt(num2, 2));
}

- thelineofcode December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

Sorry, this is a silly answer. If you write this, the will ask you to implement parseInt, opening up a big can of worms.

If they ask you to write a function for copying a string, you won't use memcpy/strcpy, would you?

- Anonymous December 17, 2013 | Flag
Comment hidden because of low score. Click to expand.


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More