0

http://www.glassdoor.com/Interview/Facebook-Interview-Questions-E40772.htmでいくつかのインタビューの質問を見ているときに、次の質問に出くわしました。

2 進数の 2 つの文字列表現 (例: "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';

次に、逆イテレータを使用するか、インデックスのみを使用して、3 つの文字列をループします (これにより、各文字列の同じ要素に確実にアクセスできます)。

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

ループ内では、実際には 4 つの可能性しかありません。「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';

最後に、必要に応じて、結果の先頭のゼロを抑制し (最大で 1 つ)、それをアサートすることもできます carry == '0'(そうでない場合は、サイズの計算を台無しにしてしまうため)。

于 2013-04-24T10:12:39.727 に答える
1

ここで最も難しい部分は、文字列を右から左に処理する必要があるという事実です。これは、次のいずれかで実行できます。

  • 文字列を逆にする (入力と出力)。
  • 再帰呼び出しでは、「戻る」ときにビットを処理します。つまり、最初に「次のビット」で再帰加算を呼び出し、次に「現在のビット」を加算します。
  • 逆反復子を使用して、結果を右から左に構築します。問題は、結果の長さを事前に知る方法です (どこから始めればよいかがわかります)。

数値が大きい場合、再帰的な解決策には問題があります。つまり、スタックがオーバーフローする可能性があります。

文字列を逆にするのが最も簡単な解決策ですが、最も効率的な解決策ではありません。

1 番目と 3 番目のオプションの組み合わせは、逆反復子を使用して入力文字列を逆に処理しますが、結果を逆の順序で構築し (ビットを単純に追加できるように)、結果を逆にします。

これは多かれ少なかれあなたのアプローチでもあります。ループ カウントiを実装jし、文字列の長さから 1 (!) を引いた値から 0 まで、入力文字列を逆の順序でウォークスルーします。が true に設定されている場合carry、次の反復でビット合計に 1 を追加します。のビット合計を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 に答える