Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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;
}
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
Am I wrong in assuming what they want you to *bitwise OR* both numbers
0b100011 | 0b100100 = 0b1000111
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;
}
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;
}
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;
}}
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();
}
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;
}
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))
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
#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;
}
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)))
#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
#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;
}
#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;
}
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;
}
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);
}
}
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;
}
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");
}
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]];
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);
}
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];
}
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();
}
}
// 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;
}
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]);
}
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);
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
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);
}
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;
}
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;
}
#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);
}
~
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
}
}
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;
}
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));
}
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?
Theory
sum = a xor b xor c
carry = ab + bc+ ac
Code
- Saurabh2816 December 17, 2013