Amazon Interview Question
Country: United States
Good point Rahul, not only 'aux' must be zero but also 'k' must exceeds length of at least one string. Bug fixed, thank you!
public static String sumBinary(String binary1, String binary2)
{
char[] binary1Array = binary1.toCharArray();
char[] binary2Array = binary2.toCharArray();
int length = binary1.length() > binary2.length() ? binary1.length() + 1 : binary2.length() +1;
char[] sum = new char[length];
int i=binary1Array.length-1, j=binary2Array.length-1, k= length-1;
char carry = '0';
while (i >= 0 && j >= 0)
{
if (binary1Array[i] == '0' && binary2Array[j] == '0' && carry == '0') { sum[k] = '0'; carry = '0'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '0' && carry == '0') { sum[k] = '1'; carry = '0'; } else
if (binary1Array[i] == '0' && binary2Array[j] == '1' && carry == '0') { sum[k] = '1'; carry = '0'; } else
if (binary1Array[i] == '0' && binary2Array[j] == '0' && carry == '1') { sum[k] = '1'; carry = '0'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '1' && carry == '0') { sum[k] = '0'; carry = '1'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '0' && carry == '1') { sum[k] = '0'; carry = '1'; } else
if (binary1Array[i] == '0' && binary2Array[j] == '1' && carry == '1') { sum[k] = '0'; carry = '1'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '1' && carry == '1') { sum[k] = '1'; carry = '1'; }
i--;
j--;
k--;
}
if (i < 0 && j >=0)
{
while (j >=0)
{
if (binary2Array[j] == '1' && carry == '0') {sum[k] = '1'; carry = '0';} else
if (binary2Array[j] == '0' && carry == '1') {sum[k] = '1'; carry = '0';} else
if (binary2Array[j] == '1' && carry == '1') {sum[k] = '0'; carry = '1';}
j--;
k--;
}
}
if ( j < 0 && i >= 0)
{
while (i >=0)
{
if (binary1Array[i] == '1' && carry == '0') {sum[k] = '1'; carry = '0';} else
if (binary1Array[i] == '0' && carry == '1') {sum[k] = '1'; carry = '0';} else
if (binary1Array[i] == '1' && carry == '1') {sum[k] = '0'; carry = '1';}
i--;
k--;
}
}
if (carry == '1') sum[k] = carry;
return new String(sum);
}
I have created a solution with code clearance/quality in mind. So, I divided it into two methods that could be reused:
/**
* Created by sky on 21/04/15.
*/
public class SumBinary {
public static int binaryStringToInteger(String binary) {
int a = 0;
int mul = 1;
for (int i = binary.length() - 1; i >= 0; i--) {
Character chr = binary.charAt(i);
int bit = chr == '1' ? 1 : 0;
a += bit * mul;
mul <<= 1;
}
return a;
}
public static String integerToBinaryString(int v) {
int mask = 1;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 32; i++) {
if ((v & mask) > 0) {
sb.append('1');
} else {
sb.append('0');
}
mask <<= 1;
}
String bin = sb.reverse().toString();
int idx = bin.indexOf('1');
return bin.substring(idx);
}
public static String sumBinary(String binary1, String binary2) {
int a = 0;
int b = 0;
a = binaryStringToInteger(binary1);
b = binaryStringToInteger(binary2);
int res = a + b;
return integerToBinaryString(res);
}
public static void main(String[] args) {
System.out.println(sumBinary("0111101", "1101"));
}
}
Summing the binary bits and carry bit and based on total sum choosing possibilities,
sum=3 or 2 ==> carry=1 else carry=0
public class BinarySum {
public static void main(String[] args) {
String str1="0111101",str2="1101";
int i=str1.length()-1,j=str2.length()-1;
char[] str1Array=str1.toCharArray();
char[] str2Array=str2.toCharArray();
int max=(i>=j)?i:j;
char[] sumArray=new char[max+1];
int b1,b2,sum,carry=0;
for(int k=0;k<=max;k++,i--,j--){
b1=(i>=0)?Character.getNumericValue(str1Array[i]):0;
b2=(j>=0)?Character.getNumericValue(str2Array[j]):0;
sum=b1+b2+carry;
if(sum==3){
sumArray[max-k]=Character.forDigit(1, 10);
carry=1;
}else if(sum==2){
sumArray[max-k]=Character.forDigit(0, 10);
carry=1;
}
else{
sumArray[max-k]=Character.forDigit(sum, 10);
carry=0;
}
}
String s=new String(sumArray);
System.out.println(s);
}
}
Convert to int then sum then convert it back
public void SumString(string s1, string s2)
{
Console.WriteLine(ConvertDecimalToBinaryString((ConvertBinaryToDecimal(s1) + ConvertBinaryToDecimal(s2))));
}
private int ConvertBinaryToDecimal(string str)
{
int num = 0;
int length = str.Length - 1;
for (int i = str.Length - 1; i >= 0; i--)
{
num += int.Parse(str[i].ToString()) * (int)Math.Pow(2, length - i);
}
return num;
}
private string ConvertDecimalToBinaryString(int num)
{
StringBuilder sb = new StringBuilder();
while (num != 0)
{
sb.Insert(0, num % 2);
num = num / 2;
}
return sb.ToString();
}
it.... is not good code but its work.
public class SumBinary {
public static String sumBinary(String s1, String s2) {
char[] a, b;
if(s1.length()>s2.length()){
a = s1.toCharArray();
b = s2.toCharArray();
}else {
b = s1.toCharArray();
a = s2.toCharArray();
}
int length = s1.length() > s2.length() ? s1.length() + 1 : s2.length() + 1;
char[] sum = new char[length];
char c = '0';
int i = s1.length() - 1, j = s2.length() - 1; //for looks code easy
while( i>=0 ) {
if(a[i] == '0' && c == '0') {
if(j<0) sum[i+1] = '0';
else
sum[i+1] = b[j];
}else if(a[i] == '0' && c == '1') {
if(j<0) {
sum[i+1] = '1';
c = '0';
}else if(b[j] == '0') {
sum[i+1] = '1';
c = '0';
}else{
sum[i+1] = '0';
c = '1';
}
}else if(a[i] == '1' && c == '1') {
if(j<0) {
sum[i+1] = '0';
c = '1';
}else if(b[j] == '0') {
sum[i+1] = '0';
c = '1';
}else{
sum[i+1] = '1';
c = '1';
}
}else if(a[i] == '1' && c == '0') {
if(j<0) {
sum[i+1] = '1';
//c == '0';
} else if(b[j] == '0') {
sum[i+1] = '1';
}else {
sum[i+1] = '0';
c='1';
}
}
i--;
j--;
}
if(c == '1') sum[0] = '1';
// System.out.println(sum);
return new String(sum); // or return sum?
}
public static void main(String[] args) {
System.out.println(sumBinary("", ""));
System.out.println(sumBinary("0", "0"));
System.out.println(sumBinary("1", "1"));
System.out.println(sumBinary("0111101", "0001101"));
System.out.println(sumBinary("1111", "0000"));
System.out.println(sumBinary("1010", "0101"));
System.out.println(sumBinary("1111", "1111"));
System.out.println(sumBinary("1111", ""));
System.out.println(sumBinary("1111", "1"));
System.out.println(sumBinary("1111", "00"));
System.out.println(sumBinary("1111111111111111", "111"));
}
}
public class SumBinary {
public static String sumBinary(String s1, String s2) {
char[] a, b;
if(s1.length()>s2.length()){
a = s1.toCharArray();
b = s2.toCharArray();
}else {
b = s1.toCharArray();
a = s2.toCharArray();
}
int length = s1.length() > s2.length() ? s1.length() + 1 : s2.length() + 1;
char[] sum = new char[length];
char c = '0';
int i = s1.length() - 1, j = s2.length() - 1; //for looks code easy
while( i>=0 ) {
if(a[i] == '0' && c == '0') {
if(j<0) sum[i+1] = '0';
else
sum[i+1] = b[j];
}else if(a[i] == '0' && c == '1') {
if(j<0) {
sum[i+1] = '1';
c = '0';
}else if(b[j] == '0') {
sum[i+1] = '1';
c = '0';
}else{
sum[i+1] = '0';
c = '1';
}
}else if(a[i] == '1' && c == '1') {
if(j<0) {
sum[i+1] = '0';
c = '1';
}else if(b[j] == '0') {
sum[i+1] = '0';
c = '1';
}else{
sum[i+1] = '1';
c = '1';
}
}else if(a[i] == '1' && c == '0') {
if(j<0) {
sum[i+1] = '1';
//c == '0';
} else if(b[j] == '0') {
sum[i+1] = '1';
}else {
sum[i+1] = '0';
c='1';
}
}
i--;
j--;
}
if(c == '1') sum[0] = '1';
// System.out.println(sum);
return new String(sum); // or return sum?
}
public static void main(String[] args) {
System.out.println(sumBinary("", ""));
System.out.println(sumBinary("0", "0"));
System.out.println(sumBinary("1", "1"));
System.out.println(sumBinary("0111101", "0001101"));
System.out.println(sumBinary("1111", "0000"));
System.out.println(sumBinary("1010", "0101"));
System.out.println(sumBinary("1111", "1111"));
System.out.println(sumBinary("1111", ""));
System.out.println(sumBinary("1111", "1"));
System.out.println(sumBinary("1111", "00"));
System.out.println(sumBinary("1111111111111111", "111"));
}
}
I hope my Java solution is easy to read and understand:
String binarySum(String n1, String n2){
if (n2.length() > n1.length()){
String tmp = n1;
n1 = n2;
n2 = tmp;
}
StringBuilder sum = new StringBuilder();
int carry = 0;
for (int i = 0; i < n1.length(); i++){
int idx1 = n1.length() - 1 - i;
int bit1 = n1.charAt(idx1) - '0';
int bit2 = 0;
int idx2 = n2.length() - 1 - i;
if (idx2 >= 0){
bit2 = n2.charAt(idx2) - '0';
}
int bitSum = bit1 + bit2 + carry;
if (bitSum >= 2){
carry = 1;
}
else {
carry = 0;
}
bitSum %= 2;
sum.append((char)(bitSum + '0'));
}
if (carry == 1){
sum.append('1');
}
return sum.reverse().toString();
}
I see a lot of brute force like methods. Although my answer is probably not what the interviewer is looking for it can be solved much simpler.
string sumBinary(string s1,string s2)
{
string sum;
int result = (std::stoull(s1.c_str(),NULL,2) + std::stoull(s2.c_str(),NULL,2));
while(result != 0)
{
if(result & 0x1)
{
sum = "1" + sum;
}else
{
sum = "0" + sum;
}
result >>= 1;
}
return sum;
}
My clean java code
public String sumBinary (String a, String b){
int carrier = 0 ;
StringBuilder sb = new StringBuilder ();
int i = a.length() - 1 , j = b.length() - 1 ;
while (i >= 0 || j >= 0) {
int v1 = i < 0 ? 0 : a.charAt(i) - '0' ;
int v2 = j <0 ? 0 : b.charAt(j) - '0' ;
int sum = v1 + v2 + carrier ;
sb.append(sum % 2) ;
carrier = sum / 2 ;
i--;
j--;
}
if (carrier == 1) {
sb.append(carrier) ;
}
sb.reverse() ;
return sb.toString() ;
}
private static String sumBinary(String binary1, String binary2)
{
String binary_sum = "";
int carry = 0;
for(int cnt1 = binary1.length()-1,cnt2 = binary2.length()-1; cnt1 >= 0 || cnt2 >=0; cnt1--,cnt2--)
{
int digit1 = 0;
int digit2 = 0;
if(cnt1 >= 0)
digit1 = new Integer(binary1.charAt(cnt1)) - '0';
if(cnt2 >=0)
digit2 = new Integer(binary2.charAt(cnt2)) - '0';
int sum = digit1 + digit2 + carry;
switch(sum)
{
case 0:
binary_sum = "0"+binary_sum;
carry = 0;
break;
case 1:
binary_sum = "1"+binary_sum;
carry = 0;
break;
case 2:
binary_sum = "0"+binary_sum;
carry = 1;
break;
case 3:
binary_sum = "1"+binary_sum;
carry = 1;
break;
}
}
if(carry > 0)
binary_sum = "1"+binary_sum;
return binary_sum;
}
#include<iostream>
#include<string.h>
using namespace std;
#define GET_VAL(a) (a=='1'?1:0)
#define GET_STR(a) (a?'1':'0')
int add(const char a, const char b)
{
if(GET_VAL(a) && GET_VAL(b))
return 10;
else
return (GET_VAL(a) | GET_VAL(b));
}
main()
{
std::string a = "0100101";//"0111101";
std::string b = "1101110";//"1101";
std::string exp = "10010011";//"1001010";
std::string smallNum, bigNum, result;
int diff = 0;
if(a.length() < b.length())
{
bigNum = b;
smallNum = a;
diff = b.length() - a.length();
}
else
{
bigNum = a;
smallNum = b;
diff = a.length() - b.length();
}
for(int i=0;i<diff;i++)
{
smallNum = '0' + smallNum;
}
int carry = 0, j=0;
for(j=smallNum.length()-1;j>=0;j--)
{
int val = add(bigNum[j],smallNum[j]);
if(carry < 10 && val < 10)
carry = add(GET_STR(carry),GET_STR(val));
else
carry += val;
int rem = (carry % 10);
result = GET_STR(rem) + result;
carry = carry / 10;
}
if(carry)
result = GET_STR(carry) + result;
cout<<"\nstring 1: "<<bigNum<<"\nstring 2: "<<smallNum<<"\nexpected: "<<exp;
if(exp == result)
cout<<"\nPerfect result : "<<result<<endl;
else
cout<<"\nwrong result : "<<result<<endl;
}
#include<iostream>
#include<string.h>
using namespace std;
#define GET_VAL(a) (a=='1'?1:0)
#define GET_STR(a) (a?'1':'0')
int add(const char a, const char b)
{
if(GET_VAL(a) && GET_VAL(b))
return 10;
else
return (GET_VAL(a) | GET_VAL(b));
}
main()
{
std::string a = "0100101";//"0111101";
std::string b = "1101110";//"1101";
std::string exp = "10010011";//"1001010";
std::string smallNum, bigNum, result;
int diff = 0;
if(a.length() < b.length())
{
bigNum = b;
smallNum = a;
diff = b.length() - a.length();
}
else
{
bigNum = a;
smallNum = b;
diff = a.length() - b.length();
}
for(int i=0;i<diff;i++)
{
smallNum = '0' + smallNum;
}
int carry = 0, j=0;
for(j=smallNum.length()-1;j>=0;j--)
{
int val = add(bigNum[j],smallNum[j]);
if(carry < 10 && val < 10)
carry = add(GET_STR(carry),GET_STR(val));
else
carry += val;
int rem = (carry % 10);
result = GET_STR(rem) + result;
carry = carry / 10;
}
if(carry)
result = GET_STR(carry) + result;
cout<<"\nstring 1: "<<bigNum<<"\nstring 2: "<<smallNum<<"\nexpected: "<<exp;
if(exp == result)
cout<<"\nPerfect result : "<<result<<endl;
else
cout<<"\nwrong result : "<<result<<endl;
}
#define GET_VAL(a) (a=='1'?1:0)
#define GET_STR(a) (a?'1':'0')
int add(const char a, const char b)
{
if(GET_VAL(a) && GET_VAL(b))
return 10;
else
return (GET_VAL(a) | GET_VAL(b));
}
main()
{
std::string a = "0100101";//"0111101";
std::string b = "1101110";//"1101";
std::string exp = "10010011";//"1001010";
std::string smallNum, bigNum, result;
int diff = 0;
if(a.length() < b.length())
{
bigNum = b;
smallNum = a;
diff = b.length() - a.length();
}
else
{
bigNum = a;
smallNum = b;
diff = a.length() - b.length();
}
for(int i=0;i<diff;i++)
{
smallNum = '0' + smallNum;
}
int carry = 0, j=0;
for(j=smallNum.length()-1;j>=0;j--)
{
int val = add(bigNum[j],smallNum[j]);
if(carry < 10 && val < 10)
carry = add(GET_STR(carry),GET_STR(val));
else
carry += val;
int rem = (carry % 10);
result = GET_STR(rem) + result;
carry = carry / 10;
}
if(carry)
result = GET_STR(carry) + result;
cout<<"\nstring 1: "<<bigNum<<"\nstring 2: "<<smallNum<<"\nexpected: "<<exp;
if(exp == result)
cout<<"\nPerfect result : "<<result<<endl;
else
cout<<"\nwrong result : "<<result<<endl;
}
#include<iostream>
#include<string.h>
using namespace std;
#define GET_VAL(a) (a=='1'?1:0)
#define GET_STR(a) (a?'1':'0')
int add(const char a, const char b)
{
if(GET_VAL(a) && GET_VAL(b))
return 10;
else
return (GET_VAL(a) | GET_VAL(b));
}
main()
{
std::string a = "0100101";//"0111101";
std::string b = "1101110";//"1101";
std::string exp = "10010011";//"1001010";
std::string smallNum, bigNum, result;
int diff = 0;
if(a.length() < b.length())
{
bigNum = b;
smallNum = a;
diff = b.length() - a.length();
}
else
{
bigNum = a;
smallNum = b;
diff = a.length() - b.length();
}
for(int i=0;i<diff;i++)
{
smallNum = '0' + smallNum;
}
int carry = 0, j=0;
for(j=smallNum.length()-1;j>=0;j--)
{
int val = add(bigNum[j],smallNum[j]);
if(carry < 10 && val < 10)
carry = add(GET_STR(carry),GET_STR(val));
else
carry += val;
int rem = (carry % 10);
result = GET_STR(rem) + result;
carry = carry / 10;
}
if(carry)
result = GET_STR(carry) + result;
cout<<"\nstring 1: "<<bigNum<<"\nstring 2: "<<smallNum<<"\nexpected: "<<exp;
if(exp == result)
cout<<"\nPerfect result : "<<result<<endl;
else
cout<<"\nwrong result : "<<result<<endl;
}
#include<iostream>
#include<string.h>
using namespace std;
#define GET_VAL(a) (a=='1'?1:0)
#define GET_STR(a) (a?'1':'0')
int add(const char a, const char b)
{
if(GET_VAL(a) && GET_VAL(b))
return 10;
else
return (GET_VAL(a) | GET_VAL(b));
}
main()
{
std::string a = "0100101";//"0111101";
std::string b = "1101110";//"1101";
std::string exp = "10010011";//"1001010";
std::string smallNum, bigNum, result;
int diff = 0;
if(a.length() < b.length())
{
bigNum = b;
smallNum = a;
diff = b.length() - a.length();
}
else
{
bigNum = a;
smallNum = b;
diff = a.length() - b.length();
}
for(int i=0;i<diff;i++)
{
smallNum = '0' + smallNum;
}
int carry = 0, j=0;
for(j=smallNum.length()-1;j>=0;j--)
{
int val = add(bigNum[j],smallNum[j]);
if(carry < 10 && val < 10)
carry = add(GET_STR(carry),GET_STR(val));
else
carry += val;
int rem = (carry % 10);
result = GET_STR(rem) + result;
carry = carry / 10;
}
if(carry)
result = GET_STR(carry) + result;
cout<<"\nstring 1: "<<bigNum<<"\nstring 2: "<<smallNum<<"\nexpected: "<<exp;
if(exp == result)
cout<<"\nPerfect result : "<<result<<endl;
else
cout<<"\nwrong result : "<<result<<endl;
}
class SolutionForSumOfTwoBinaryGivenInStringFormat {
public String solution(String str1, String str2) {
String out = "";
String first = str1;
String secnd = str2;
if (str2.length() > str1.length()) {
first = str2;
secnd = str1;
}
int j = secnd.length() - 1;
int carry = 0;
for (int i = first.length() - 1; i >= 0; i--) {
int temp1 = first.charAt(i) - '0';
int temp2 = 0;
if (j >= 0) {
temp2 = secnd.charAt(j--) - '0';
}
int sum = temp1 + temp2 + carry;
// System.out.println("TEMP1: " + temp1 + "\t TEMP2: " + temp2 + "\t CARRY: " + carry +
// "\t SUM: " + sum);
if (sum == 0) {
out = '0' + out;
carry = 0;
} else if (sum == 1) {
out = '1' + out;
carry = 0;
} else if (sum == 2) {
out = '0' + out;
carry = 1;
} else if (sum == 3) {
out = '1' + out;
carry = 1;
} else {
System.out.println("Invalid Entry");
return null;
}
}
if(carry != 0) {
return carry + out;
}
return out;
}
}
public class SumOfTwoBinaryGivenInStringFormat {
public static void main(String[] args) {
SolutionForSumOfTwoBinaryGivenInStringFormat mSol = new SolutionForSumOfTwoBinaryGivenInStringFormat();
System.out.println(mSol.solution("0111101", "1101"));
System.out.println(mSol.solution("", ""));
System.out.println(mSol.solution("1", ""));
System.out.println(mSol.solution("10101", ""));
System.out.println(mSol.solution("1111", "11"));
System.out.println(mSol.solution("1111", "1111"));
}
}
String sumBinary(String num1, String num2) {
// Indexes to start from
int i1 = num1.length() - 1;
int i2 = num2.length() - 1;
// characters at index
int b1 = 0;
int b2 = 0;
// sum character
int c = 0;
// sum index
int si = i1 > i2 ? i1 : i2;
// sum char array
char[] sum = new char[si + 1];
// carry
int carry = 0;
// iterate until both the strings are read
while(i1 >= 0 || i2 >= 0) {
b1 = 0;
b2 = 0;
if(i1 >= 0) {
b1 = ( (int) num1.charAt(i1) ) & 0x01;
}
if(i2 >= 0) {
b2 = ( (int) num2.charAt(i2) ) & 0x01;
}
// compute sum of bits
c = b1 + b2 + carry;
// compute carry
carry = c & 0x03;
carry = carry >> 1;
// sum bit
c = c & 0x01;
// put sum bit in the sum char array
sum[si] = (char) (c + 0x30);
i1--;
i2--;
si--;
}
return new String(sum);
}
!cc
cc sumBinary.c
./a.out
0111101 + 1101 = 1001010
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// convert from string binary to integer
int atob(char *a) {
int n = strlen(a);
int num = 0;
int index = 0;
while (n-- >= 0) {
if (a[n] == '1') {
num = num + (1 << index);
}
index++;
}
return num;
}
// convert an int to string
// the caller needs to delete the memory return
char *itobs(int myInt) {
char *c = malloc(sizeof (char) * 33);
int seenOne = 0;
int cur = 0;
for (int i = 0; i < 32; i++) {
if (myInt & (1 << (31 - i))) {
c[cur++] = '1';
seenOne = 1;
} else {
if (seenOne == 1) {
c[cur++] = '0';
}
}
}
c[cur] = '\0';
return c;
}
char *sumBinary(char *a, char *b) {
return itobs(atob(a) + atob(b));
}
int
main (int arc, char *argv[]) {
printf( "0111101 + 1101 = %s\n", sumBinary("0111101", "1101"));
}
char *sumBinary(char *st1, char *st2)
{
char *str1, *str2, *str3;
int length,carry=0,res=0;
if(strlen(st1) > strlen(st2))
{
srt1=st1;
str2=st2;
str3=(char *) malloc (strlen(st1)+1);
}
else
{
srt1=st2;
str2=st1;
str3=(char *) malloc (strlen(st2)+1);
}
length1=strlen(str1);
length2=strlen(str2);
while (length2>=0)
{
res = (str1[length1] - '0') + (str2[length2] - '0') + carry;
str3[length1+1] = (char)((res % 2) + '0');
carry = res / 2;
length1--;
length2--;
}
while (length1>=0)
{
res = (str1[length1] - '0') + carry;
str3[length1+1] = (char)(res % 2 + '0');
carry = res / 2;
length1--;
}
str3[0]=(char)(carry + '0');
return str3;
}
My approach would be just convert binary numbers to integers (simple multiplication by power of 2), then add two decimals. Let k be number length binary number. So binary to decimal conversion will take O(n) time. Convert decimal answer back to binary. (log (k) time.)
This will avoid most of heavy if - else loops
public class BinaryAddition {
public static void main(String[] args){
String a="0111101";
String b="1101";
int num1=Integer.parseInt(a,2);
int num2=Integer.parseInt(b,2);
System.out.println(num1+ " " +num2);
int sum=num1+num2;
String tot=Integer.toBinaryString(sum);
System.out.println("Total:" +tot);
}
}
public class BinaryAddition {
public static void main(String[] args){
String a="0111101";
String b="1101";
int num1=Integer.parseInt(a,2);
int num2=Integer.parseInt(b,2);
System.out.println(num1+ " " +num2);
int sum=num1+num2;
String tot=Integer.toBinaryString(sum);
System.out.println("Total:" +tot);
}
}
public class BinaryAddition {
public static void main(String[] args){
String a="0111101";
String b="1101";
int num1=Integer.parseInt(a,2);
int num2=Integer.parseInt(b,2);
System.out.println(num1+ " " +num2);
int sum=num1+num2;
String tot=Integer.toBinaryString(sum);
System.out.println("Total:" +tot);
}
}
public class BinaryAddition {
public static void main(String[] args){
String a="0111101";
String b="1101";
int num1=Integer.parseInt(a,2);
int num2=Integer.parseInt(b,2);
System.out.println(num1+ " " +num2);
int sum=num1+num2;
String tot=Integer.toBinaryString(sum);
System.out.println("Total:" +tot);
}
}
public class BinaryAddition {
public static void main(String[] args){
String a="0111101";
String b="1101";
int num1=Integer.parseInt(a,2);
int num2=Integer.parseInt(b,2);
System.out.println(num1+ " " +num2);
int sum=num1+num2;
String tot=Integer.toBinaryString(sum);
System.out.println("Total:" +tot);
}
}
public class BinaryAddition {
public static void main(String[] args){
String a="0111101";
String b="1101";
int num1=Integer.parseInt(a,2);
int num2=Integer.parseInt(b,2);
System.out.println(num1+ " " +num2);
int sum=num1+num2;
String tot=Integer.toBinaryString(sum);
System.out.println("Total:" +tot);
}
}
public class BinaryAddition {
public static void main(String[] args){
String a="0111101";
String b="1101";
int num1=Integer.parseInt(a,2);
int num2=Integer.parseInt(b,2);
System.out.println(num1+ " " +num2);
int sum=num1+num2;
String tot=Integer.toBinaryString(sum);
System.out.println("Total:" +tot);
}
}
public class BinaryAddition {
public static void main(String[] args){
String a="0111101";
String b="1101";
int num1=Integer.parseInt(a,2);
int num2=Integer.parseInt(b,2);
System.out.println(num1+ " " +num2);
int sum=num1+num2;
String tot=Integer.toBinaryString(sum);
System.out.println("Total:" +tot);
}
}
public class BinaryAddition {public static void main(String[] args){String a="0111101";String b="1101";int num1=Integer.parseInt(a,2);int num2=Integer.parseInt(b,2);
System.out.println(num1+ " " +num2);int sum=num1+num2;String tot=Integer.toBinaryString(sum);System.out.println("Total:" +tot);}}
public class BinaryAddition {public static void main(String[] args){String a="0111101";String b="1101";int num1=Integer.parseInt(a,2);int num2=Integer.parseInt(b,2);
System.out.println(num1+ " " +num2);int sum=num1+num2;String tot=Integer.toBinaryString(sum);System.out.println("Total:" +tot);}}
package proj2;
public class AddBinaryStrings {
public AddBinaryStrings(String string, String string2) {
int carry = 0;
int i = string.length()-1;
int j = string2.length()-1;
StringBuilder sb = new StringBuilder();
while(i >=0 && j >=0){
int a = string.charAt(i)-'0';
int b = string2.charAt(j)-'0';
int c = a + b + carry;
sb.append(c%2);
carry = c/2;
i--;
j--;
}
while(i >= 0){
int a = string.charAt(i)-'0';
int c = a + carry;
sb.append(c%2);
carry = c/2;
i--;
}
while(j >= 0){
int b = string2.charAt(j)-'0';
int c = b + carry;
sb.append(c%2);
carry = c/2;
j--;
}
if (carry == 1) {
sb.append(carry) ;
}
sb.reverse() ;
System.out.println(sb);
}
}
public static String sumBinary(String binary1, String binary2)
{
char[] binary1Array = binary1.toCharArray();
char[] binary2Array = binary2.toCharArray();
int length = binary1.length() > binary2.length() ? binary1.length() + 1 : binary2.length() +1;
char[] sum = new char[length];
int i=binary1Array.length-1, j=binary2Array.length-1, k= length-1;
char carry = '0';
while (i >= 0 && j >= 0)
{
if (binary1Array[i] == '0' && binary2Array[j] == '0' && carry == '0') { sum[k] = '0'; carry = '0'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '0' && carry == '0') { sum[k] = '1'; carry = '0'; } else
if (binary1Array[i] == '0' && binary2Array[j] == '1' && carry == '0') { sum[k] = '1'; carry = '0'; } else
if (binary1Array[i] == '0' && binary2Array[j] == '0' && carry == '1') { sum[k] = '1'; carry = '0'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '1' && carry == '0') { sum[k] = '0'; carry = '1'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '0' && carry == '1') { sum[k] = '0'; carry = '1'; } else
if (binary1Array[i] == '0' && binary2Array[j] == '1' && carry == '1') { sum[k] = '0'; carry = '1'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '1' && carry == '1') { sum[k] = '1'; carry = '1'; }
i--;
j--;
k--;
}
if (i < 0 && j >=0)
{
while (j >=0)
{
if (binary2Array[j] == '1' && carry == '0') {sum[k] = '1'; carry = '0';} else
if (binary2Array[j] == '0' && carry == '1') {sum[k] = '1'; carry = '0';} else
if (binary2Array[j] == '1' && carry == '1') {sum[k] = '0'; carry = '1';}
j--;
k--;
}
}
if ( j < 0 && i >= 0)
{
while (i >=0)
{
if (binary1Array[i] == '1' && carry == '0') {sum[k] = '1'; carry = '0';} else
if (binary1Array[i] == '0' && carry == '1') {sum[k] = '1'; carry = '0';} else
if (binary1Array[i] == '1' && carry == '1') {sum[k] = '0'; carry = '1';}
i--;
k--;
}
}
if (carry == '1') sum[k] = carry;
return new String(sum);
}
public static String sumBinary(String binary1, String binary2)
{
char[] binary1Array = binary1.toCharArray();
char[] binary2Array = binary2.toCharArray();
int length = binary1.length() > binary2.length() ? binary1.length() + 1 : binary2.length() +1;
char[] sum = new char[length];
int i=binary1Array.length-1, j=binary2Array.length-1, k= length-1;
char carry = '0';
while (i >= 0 && j >= 0)
{
if (binary1Array[i] == '0' && binary2Array[j] == '0' && carry == '0') { sum[k] = '0'; carry = '0'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '0' && carry == '0') { sum[k] = '1'; carry = '0'; } else
if (binary1Array[i] == '0' && binary2Array[j] == '1' && carry == '0') { sum[k] = '1'; carry = '0'; } else
if (binary1Array[i] == '0' && binary2Array[j] == '0' && carry == '1') { sum[k] = '1'; carry = '0'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '1' && carry == '0') { sum[k] = '0'; carry = '1'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '0' && carry == '1') { sum[k] = '0'; carry = '1'; } else
if (binary1Array[i] == '0' && binary2Array[j] == '1' && carry == '1') { sum[k] = '0'; carry = '1'; } else
if (binary1Array[i] == '1' && binary2Array[j] == '1' && carry == '1') { sum[k] = '1'; carry = '1'; }
i--;
j--;
k--;
}
if (i < 0 && j >=0)
{
while (j >=0)
{
if (binary2Array[j] == '1' && carry == '0') {sum[k] = '1'; carry = '0';} else
if (binary2Array[j] == '0' && carry == '1') {sum[k] = '1'; carry = '0';} else
if (binary2Array[j] == '1' && carry == '1') {sum[k] = '0'; carry = '1';}
j--;
k--;
}
}
if ( j < 0 && i >= 0)
{
while (i >=0)
{
if (binary1Array[i] == '1' && carry == '0') {sum[k] = '1'; carry = '0';} else
if (binary1Array[i] == '0' && carry == '1') {sum[k] = '1'; carry = '0';} else
if (binary1Array[i] == '1' && carry == '1') {sum[k] = '0'; carry = '1';}
i--;
k--;
}
}
if (carry == '1') sum[k] = carry;
return new String(sum);
}
use sum and carry technique
Sum(string s1, string s2)
{
int [] n1 = new int[s1.Length];
int [] n2 = new int[s2.Length];
int max = s1.Length > s2.Length ? s1.Length:S2.Length;
for(i=0;i<s1.Length;i++) n1[s1.Length - 1 - i] = (s1.charAt(i) == '0') ? 0 : 1;
for(i=0;i<s2.Length;i++) n2[s2.Length - 1 - i] = (s2.charAt(i) == '0') ? 0 : 1;
int carry = new int[((s1.Length > s2.Length) ? s1.Length + 1 : s2.Length + 1) * 2];
int sum = new int[(s1.Length > s2.Length) ? s1.Length + 1 : s2.Length + 1];
bool loop = false;
int i=0;
do
{
loop = false;
if(i==0)
{
for(i=0;i<max;i++)
{
sum[i] = ((i<s1.Length) ? s1[i] : 0) ^ ((i<s2.Length) ? s2[i] : 0);
carry[i+1] = ((i<s1.Length) ? s1[i] : 0) & ((i<s2.Length) ? s2[i] : 0);
loop |= (carry[i+1] == 1) ? true ? false;
}
}
else
{
for(i=0;i<max;i++)
{
sum[i] = (sum[i]) ^ (carry[i]);
carry[i+1] = (sum[i]) & (carry[i]);
loop |= (carry[i+1] == 1) ? true ? false;
}
max = i+1;
}
}while(loop);
StringBuilder sb = new StringBuilder();
for(i=max;i>=0;i--) sb.append(sum[i]);
return sb.ToString();
}
def sumbinaryNo(val1,val2):
maxlen = len(val1)
sumStr = ""
addDigit=0
char0 = "0"
char1="0"
extraZero = 0
extraZeroStr = ""
if len(val2)>len(val1):
extraZero = len(val2)-len(val1)
maxlen = len(val2)
print("extraZero "+str(extraZero))
for i in range(0,extraZero):
extraZeroStr = "0"+extraZeroStr
val1 = extraZeroStr+val1
elif len(val1)>len(val2):
extraZero = len(val1)-len(val2)
maxlen = len(val1)
for i in range(0,extraZero):
extraZeroStr = "0"+extraZeroStr
val2 = extraZeroStr+val2
print(val1)
print(val2)
for i in range(maxlen-1,-1,-1):
# print(i)
char0 = int(val1[i])
char1 = int(val2[i])
print(char0+char1+addDigit)
if char0+char1+addDigit == 3:
sumStr = "1"+sumStr;
addDigit = 1
elif char0+char1+addDigit == 2:
sumStr = "0"+sumStr;
addDigit = 1
else:
sumStr = str(char0+char1+addDigit)+sumStr;
addDigit = 0
print(str(addDigit)+sumStr)
sumbinaryNo('11001111','101000000')
using System;
namespace binary
{
class binarySum
{
public static string result = string.Empty;
public static int carryOver = 0;
static void Main(string[] args)
{
Console.WriteLine(sumBinary("0111101", "1101"));
Console.Read();
}
public static string sumBinary(string number1, string number2)
{
if (string.IsNullOrEmpty(number1))
{
if (string.IsNullOrEmpty(number2))
return string.Empty;
return number2;
}
if (string.IsNullOrEmpty(number2))
return number1;
int upperLimit = Math.Max(number1.Length, number2.Length);
int n1 = number1.Length;
int n2 = number2.Length;
int val1 = 0, val2 = 0, sum = 0;
for (int i = 1; i < upperLimit; i++)
{
if (n1 - i > -1 && n2 - i > -1)
{
val1 = int.Parse(number1[n1 - i].ToString());
val2 = int.Parse(number2[n2 - i].ToString());
sum = val1 + val2 + carryOver;
setBit(sum);
}
else if (n1 - i > -1)
{
val1 = int.Parse(number1[n1 - i].ToString());
sum = val1 + carryOver;
setBit(sum);
}
else if (n2 - i > -1)
{
val2 = int.Parse(number2[n2 - i].ToString());
sum = val2 + carryOver;
setBit(sum);
}
}
if (carryOver == 1)
return 1 + result;
return result;
}
public static void setBit(int sum)
{
switch (sum)
{
case 0:
result = result.Insert(0, "0");
carryOver = 0;
break;
case 1:
result = result.Insert(0, "1");
carryOver = 0;
break;
case 2:
result = result.Insert(0, "0");
carryOver = 1;
break;
case 3:
result = result.Insert(0, "1");
carryOver = 1;
break;
default:
break;
}
}
}
}
#include<iostream>
#include<string.h>
using namespace std;
#define GET_VAL(a) (a=='1'?1:0)
#define GET_STR(a) (a?'1':'0')
int add(const char a, const char b)
{
if(GET_VAL(a) && GET_VAL(b))
return 10;
else
return (GET_VAL(a) | GET_VAL(b));
}
main()
{
std::string a = "0100101";//"0111101";
std::string b = "1101110";//"1101";
std::string exp = "10010011";//"1001010";
std::string smallNum, bigNum, result;
int diff = 0;
if(a.length() < b.length())
{
bigNum = b;
smallNum = a;
diff = b.length() - a.length();
}
else
{
bigNum = a;
smallNum = b;
diff = a.length() - b.length();
}
for(int i=0;i<diff;i++)
{
smallNum = '0' + smallNum;
}
int carry = 0, j=0;
for(j=smallNum.length()-1;j>=0;j--)
{
int val = add(bigNum[j],smallNum[j]);
if(carry < 10 && val < 10)
carry = add(GET_STR(carry),GET_STR(val));
else
carry += val;
int rem = (carry % 10);
result = GET_STR(rem) + result;
carry = carry / 10;
}
if(carry)
result = GET_STR(carry) + result;
cout<<"\nstring 1: "<<bigNum<<"\nstring 2: "<<smallNum<<"\nexpected: "<<exp;
if(exp == result)
cout<<"\nPerfect result : "<<result<<endl;
else
cout<<"\nwrong result : "<<result<<endl;
}
I would prose the following solution:
(i) Extract k-th digits from the end of the strings (if index exceeds dimension return '0').
(ii) Sum these digits and the carry
(iii) Compute resulting digit as modulo 2
(iv) Compute new carry as inreger division by 2
(v) Do until digits and carry are all zero.
A sample code is shown below:
- autoboli April 22, 2015