0

在浏览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)
4

3 回答 3

2

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

否则，我可能会首先对它们进行归一化，以便它们具有最大长度的结果。就像是：

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'（因为如果不是，我们已经搞砸了大小的计算）。

于 2013-04-24T10:12:39.727 回答
1

这里最困难的部分是我们需要从右到左处理字符串。我们可以通过以下方式做到这一点：

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

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

反转字符串是最简单的解决方案，但不是最有效的解决方案。

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

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

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

于 2013-04-24T09:52:03.937 回答
0

在 Python 中，您可以使用 将字符串转换为整数int，这也提供了转换的基础：

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

打印 7.

将结果转换回二进制：

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

打印 100

于 2013-04-24T09:49:23.010 回答