#define MAX(a, b) ((a) > (b) ? (a) : (b))
char* addBinary(char* a, char* b) {
	int lenA = strlen(a);
	int lenB = strlen(b);

	int len = MAX(lenA, lenB) + 1;
	char* result = malloc(sizeof(char) * (len + 1));
	result[len--] = '\0';
	char in = '0';
	int sum = 0;

	lenA--;
	lenB--;

	if(len == 0) return "0";
	
	while(lenA >= 0 && lenB >=0) {
		sum = a[lenA] + b[lenB] + in - 3 * '0';
		switch(sum) {
		case 0:
			in = '0';
			result[len] = '0';
			break;
		case 1:
			in = '0';
			result[len] = '1';
			break;
		case 2:
			in = '1';
			result[len] = '0';
			break;
		case 3:
			in = '1';
			result[len] = '1';
			break;
		}
		lenA--;
		lenB--;
		len--;
	}

	while(lenA >= 0) {
		if(in == '0') {
			result[len] = a[lenA];
		} else if(a[lenA] == '1') {
			result[len] = '0';
			in = '1';
		} else {
			result[len] = '1';
			in = '0';
		}
		lenA--;
		len--;
	}

	while(lenB >= 0) {
		if(in == '0') {
			result[len] = b[lenB];
		} else if(b[lenB] == '1') {
			result[len] = '0';
			in = '1';
		} else {
			result[len] = '1';
			in = '0';
		}
		lenB--;
		len--;
	}

	if(in == '0')
		return result + 1;

	*result = '1';
	return result;
}