专访：给出字符串

Question

虽然经过一些面试问题看http://www.glassdoor.com/Interview/Facebook-Interview-Questions-E40772.htm我碰到以下问题来添加两个二进制数：二进制数的

给定两个字符串表示（如“1001”，“10”）编写一个函数来添加它们并返回结果作为字符串（例如“1011”）。

下面是我开始为这个问题写的一些Python代码（现在它不完整），但我不确定这是否是最好的（或者甚至是正确的）方法。我也考虑过首先在C++中实现它，但是放弃考虑字符串操作中增加的复杂性。

def add_binary(a,b): 
    temp = "" 
    carry = false 
    //i from len(a) to 1 and j from len(b) to 1 
    bit_sum = add_bit ((a[i],b[j]) 
    if (bit_sum == "10"): 
      temp.append("0") 
      carry = true 
    elif carry: 
      temp.append(add_bit("1",bit_sum)) 
    else: 
      temp.append(bit_sum) 

    return temp.reverse() 


def add_bit(b1, b2): 
    if b1 == '0': 
      return b2 
    elif b2 == '0': 
      return b1 
    elif (b1 = '1' and b2 =='1'): 
      return "10" 
    else return None 

a = "1001" 
b = "10" 
add_binary(a,b) 

Answer 1

首先，如果字符串是足够短（小于64位以下），我 可能只是将它们转换为内部整型 （unsigned long long），做加法那里，然后重新转换 的结果。在二进制字符串和 内部格式之间进行转换确实很简单。

否则，我可能会首先将它们normallize，使他们有 结果的最大长度。喜欢的东西：

size_t size = std::max(lhs.size(), rhs.size()) + 1; 
lhs.insert(lhs.begin(), size - lhs.size(), '0'); 
rhs.insert(rhs.begin(), size - rhs.size(), '0'); 

我也想创造这种规模的结果字符串：

std::string results(size, '0'); 

和进位变量，初始化为 '0'：

char carry = '0'; 

我会然后使用反向迭代器， 或更可能的，只是一个索引（这将确保访问每个字符串的相同元素）来循环三个字符串：

size_t current = size; 
while (current != 0) { 
    -- current; 
    // ... 
} 

与环中，你真的只能有四种可能性：我想 只是算上“1'（在lhs[current]，rhs[current]和 carry），并做结果的开关，设置 results[current]和carry适当：

int onesCount = 0; 
if (carry == '1') { 
    ++ onesCount; 
} 
if (lhs[current] == '1') { 
    ++ onesCount; 
} 
if (rhs[current] == '1') { 
    ++ onesCount; 
} 
swith (onesCount) { 
case 0: 
    carry = '0'; 
    results[current] = '0'; 
    break; 

case 1: 
    carry = '0'; 
    results[current] = '1'; 
    break; 

case 2: 
    carry = '1'; 
    results[current] = '0'; 
    break; 

case 3: 
    carry = '1'; 
    results[current] = '1'; 
    break; 
} 

就个人而言，我觉得这是最简单和最干净的 的解决方案，虽然有点繁琐。或者，你可以像更换 开关：

results[current] = onesCount % 2 == 0 ? '0' : '1'; 
carry = onesCount < 2 ? '0' : '1'; 

最后，如果需要的话，可以抑制 结果的任何前导零（会有至多一个），也许断言 carry == '0'（因为如果不是这样，我们已经搞砸了我们的尺寸计算方法 ）。

Answer 2

在Python中，你可以将字符串转换为整数与int，这也使得转化基地：

num = '111' 
print int(num, 2) 

打印7.

对于结果转换为二进制：

print "{:b}".format(4) 

印刷品100

Answer 3

这里最困难的部分是，我们需要从右到左处理字符串的事实。我们可以通过以下任一方式来完成此操作：

• 反转字符串（输入和输出）。
• 在递归调用，处理该比特时“回去”，即首先调用的递归上添加了“下一个位”，然后添加“当前位”。
• 使用反向迭代器并从右向左构造结果。问题仍然是如何预先知道结果的长度（所以你知道从哪里开始）。

当数字很大时，递归解决方案会出现问题，即堆栈可能会溢出。

倒车弦是最简单的解决办法，但不是最有效的一个。

在第一和第三个选项的组合将是处理使用反向迭代反向输入字符串，但构造以相反的顺序的结果（所以可以简单的附加比特），然后反转的结果。

这或多或少也是你的方法。从字符串长度减1（！）开始，执行循环计数i和j直到0，所以这将按照相反的顺序遍历输入字符串。如果carry设置为true，则在下一次迭代中将位和加1。将add_bit的位和表示为整数，而不是再次作为字符串，因此您可以添加进位。

在C++中，您可以使用rbegin()和rend()以相反顺序遍历任意序列。