[67] Add Binary

吸加加的string好方便QQ
不過還是寫的很醜
sign

Add Binary
class Solution {
public:
    string addBinary(string a, string b) {
        int lenA = a.length();
        int lenB = b.length();
        string ret;
        int i,j, flag = 0;
        for(i=lenA,j=lenB;(i>0 || j>0);i--,j--)
        {
            int anum = 0,bnum = 0;
            if (i>0)
                anum = a[i -1] - '0';
            if (j>0)
                bnum = b[j -1] - '0';

            int tmp = flag + anum + bnum;
            if (tmp > 1)
            {
                flag = 1;
                tmp -=2;
            }
            else
                flag = 0;
            ret = to_string(tmp) + ret;


        }
        if (flag>0)
            ret = "1" + ret;

        return ret;
    }
};

[20260710] 更新

奇怪別人寫就是比較漂亮 ～—～

#define max(a,b) (a>b)?(a):(b)

void reverse(char *a, char *b){

char tmp = *a;

*a=*b;

*b=tmp;

}

char* addBinary(char* a, char* b) {

int l1 = strlen(a);

int l2 = strlen(b);

int longer= max(l1, l2);

int carry = 0;

char *ret = calloc(longer+2, sizeof(char));//for additional carry & ending so it's longer +1 +1

int idx = 0;

while (longer>0){

int v1=0;

int v2=0;

if (l1-1>=0)

v1= a[--l1]-'0';

if (l2-1>=0)

v2= b[--l2]-'0';

//printf("%d + %d\n", v1, v2);

int sum = carry+v1+v2;

carry = (sum>1)? 1: 0;

ret[idx++]= ((sum& 0x1)==1)? '1' :'0';

longer--;

}

if (carry>0)

ret[idx++]='1';

//printf("idx %d carry %d\n", idx,carry);

for (int i=0; i<idx/2;i++)

reverse(&ret[i], &ret[idx-1-i]);

return ret;

}

看來while 可以改成 l1>0 || l2>0 || carry 結果又改出無窮回圈 囧

#define max(a,b) (a>b)?(a):(b)

void reverse(char *a, char *b){

char tmp = *a;

*a=*b;

*b=tmp;

}

char* addBinary(char* a, char* b) {

int l1 = strlen(a);

int l2 = strlen(b);

int longer= max(l1, l2);

int carry = 0;

char *ret = calloc(longer+2, sizeof(char));//for additional carry & ending so it's longer +1 +1

int idx = 0;

while (l1>0 || l2>0 || carry){

int v1=0;

int v2=0;

if (l1-1>=0)

v1= a[--l1]-'0';

if (l2-1>=0)

v2= b[--l2]-'0';

int sum = carry+v1+v2;

carry = (sum>1)? 1: 0;

ret[idx++]= ((sum& 0x1)==1)? '1' :'0';

}

for (int i=0; i<idx/2;i++)

reverse(&ret[i], &ret[idx-1-i]);

return ret;

}

[20260709] 更新

有一點懶得修！ 這個算是復健題XD 輸入小的時候應該是對的～

但長度一長就一定是錯的要重寫～就先貼下吧. 沒想到當年我竟然是用C++寫的XD

int str2int(char* s1, int len){

int ret=0;

for (int i=0; i<len;i++)

{

ret = (ret<<1) + (s1[i] & 0x1);

}

// printf("ret %d\n",ret);

return ret;

}

#define STRLEN INT_MAX

void swap(char *a, char *b){

char tmp = *a;

*a = *b;

*b = tmp;

return;

}

char* int2str(int val){

char *ret = calloc (STRLEN,sizeof(char));

int idx = 0;

//printf("int2str val %d\n",val);

while (val>0)

{

if (val&0x1 == 1)

ret[idx++]='1';

else

ret[idx++]='0';

val= val>>1;

//printf("int2str idx %d, [%c]\n",idx, ret[idx-1]);

}

//printf("int2str idx(len) %d\n",idx);

char *reverse= calloc(idx+1, sizeof(char));

// char *reverse = (char*) realloc(ret, idx*sizeof(char));

for (int i=0; i<idx; i++)

reverse[idx-i-1]= ret[i];

#if 0

printf("int2str idx %d, strlen %d\n",idx, strlen(reverse));

for (int i=0; i<idx/2; i++)

{

swap(&reverse[i], &reverse[idx-i]);

}

#endif

if (idx==0)

return "0";

return reverse;

}

char* addBinary(char* a, char* b) {

int l1 = strlen(a);

int l2 = strlen(b);

printf("l1 %d l2 %d\n",l1,l2);

int sum = str2int(a,l1) + str2int(b,l2);

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

return int2str(sum);

// return NULL;

}