專訪：給出字符串

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()以相反順序遍歷任意序列。