6

インタビューで次の質問がありました。実際に機能する実装を提供したと思いますが、より高速なより良い実装があるのか​​ 、それとも私が見逃したトリックがあるのか​​ 疑問に思っていました.

3 つの符号なし 30 ビット整数が与えられた場合、元の数値のいずれかと比較したときに同じ位置ビットが 1 に設定されている 30 ビット整数の数を返します。つまり、すべての 0 を列挙します。

例を挙げましょう。わかりやすくするために 4 ビットを使用します。

与えられた:

A = 1001
B = 0011
C = 0110

セットには 8 つの 4 ビット int があるため、8 を返す必要があります。セットは次のとおりです。

0011
0110
0111
1001
1011
1101
1110
1111

さて、私がどのように解決したかは、各数値を取得して一連の可能性を列挙し、すべての個別の値を数えることでした。セットを列挙する方法は、番号から始めて、それに 1 を追加してから、マスクに到達するまでそれ自体で OR することでした。数値自体がセットに含まれており、マスク (すべて 1 に設定されている) もセットに含まれています。たとえば、1001 のセットを列挙するには:

1001 = the start
1011 = (1001 + 1) | 1001
1101 = (1011 + 1) | 1001
1111 = (1101 + 1) | 1001 (this is the last value as we have reached our mask)

したがって、各番号に対してそれを行い、一意のものを数えます。

これはPythonコードです（ただし、ビット単位の操作を実行できる限り、言語は実際には問題にならないため、この質問がc/c ++にもタグ付けされている理由です）：

MASK = 0x3FFFFFFF

def count_anded_bitmasks( A, B, C ):
    andSets = set(
      enumerate_all_subsets(A) +
      enumerate_all_subsets(B) +
      enumerate_all_subsets(C)
    )
    return len(andSets)


def enumerate_all_subsets( d ):
    andSet = []
    n = d
    while n != MASK:
        andSet.append(n)
        n = (n + 1) | d
    andSet.append(n)
    return andSet

これで機能し、正しい答えが得られましたが、トリックを逃したかどうか疑問に思っています。問題はすべての値を列挙するのではなく、数だけを尋ねることだったので、おそらくもっと速い方法があります。最初に数値を組み合わせるか、列挙せずにカウントを取得します。ある感じです。多数のゼロを含む数値であるため、列挙は指数関数的に増加し、かなりの時間がかかる場合があります。

AB と C がある場合、A または B または C の対応するビットが 1 に設定されているビットが 1 に設定されている一連の数値のカウント。

質問を理解していない人もいます（最初に正しく質問しなかったことは役に立ちませんでした）。上記の指定された AB と C の値を使用してみましょう。

A:

1001
1011
1101
1111

B:

0011
0111
1011
1111

子：

0110
0111
1110
1111

これらのセットを組み合わせて、個別のエントリを数えます。それが答えです。値を列挙せずにこれを行う方法はありますか?

編集：質問を間違えてすみません。今修正しました。

4

4 に答える 4

7

編集:要件の更新: 3 つの符号なし 30 ビット整数が与えられた場合、元の数値のいずれかと比較すると、同じ位置ビットが 1 に設定されている 30 ビット整数の数を返します。つまり、すべての 0 を列挙します。

それは少し難しいです。1 つの数値を計算するのは簡単です。その場合、可能な整数の数は次のようにゼロのビット数だけに依存するためです。

// Count bits not set
const size_t NUMBITS=30;
size_t c;
size_t v = num;
for (c=NUMBITS; v; v >>= 1) 
  c -= v & 1;

return c;

素朴に、これをそれぞれに対して実行して結果を合計することにより、これを 3 つの整数に拡張しようとするかもしれませんが、可能性が一意である必要があるため、それは間違っています。

A = 1001
B = 0011
C = 0110

たとえば、1111 は 1 回ではなく 3 回数えます。任意の 2 つの数値間で共有される組み合わせの数を減算する必要がありますが、任意の組み合わせを 2 回減算しないでください。 これは、単に Winston Ewert の回答を C++ に翻訳したものです。 

size_t zeroperms(size_t v)
{
    // Count number of 0 bits
    size_t c = 1;
    for (c=NUMBITS; v; v >>= 1)
        c -= v & 1;
    // Return number of permutations possible with those bits
    return 1 << c;
}

size_t enumerate(size_t a, size_t b, size_t c)
{
    size_t total = zeroperms(a) + zeroperms(b) + zeroperms(c);
    total -= zeroperms(a | b); // counted twice, remove one
    total -= zeroperms(b | c); // counted twice, remove one
    total -= zeroperms(a | c); // counted twice, remove one
    total += zeroperms(a | b | c); // counted three times, removed three times, add one
    return total;
}
于 2012-05-01T17:29:20.237 に答える
2 
N = 4

def supers(number):
    zeros = sum(1 for bit in xrange(N) if (number >> bit) & 1 == 0)
    return 2**zeros


def solve(a,b,c):
    total = supers(a) + supers(b) + supers(c)
    total -= supers(a | b) # counted twice, remove one
    total -= supers(b | c) # counted twice, remove one
    total -= supers(a | c) # counted twice, remove one
    total += supers(a | b | c) # counted three times, removed three times, add one

    return total


print solve(0b1001,0b0011,0b0110)

説明

S(n)セット数でプロデュースさせて頂きますn。

supers(n)|S(n)|数値 n のセットのサイズを返します。supersは素晴らしい名前ではありませんが、より良い名前を思いつくのに苦労しました

コツは、それを実現することS(a) ^ S(b) = S(a | b)です。その結果、スーパーを使用して、これらすべてのセットのサイズを把握できます。

残りを理解するには、セットのベン図を描きます。

于 2012-05-01T17:55:02.383 に答える
0

トリック 1:

全体の答えは、個々の 30 ビット数の結合です。これは、ビットごとのユニオン演算子 OR に変換されます。これはD = A | B | C 、あなたの4ビットの例でできることを意味しD = 1111 ます.今、私たちは1つの数字で作業するだけです

トリック 2:

ちょっとした数学から1、可能な数のセットが 2 倍になるたびにわかることがわかります。これは、2 を 1 の数で累乗するだけでよいことを意味します。ループで 1 をカウントし、そのたびに下にシフトします

bits = 0
D = 0b1111 #our number from trick 1
for i in range(4): #here 4 is the number of bits
    if D & 1:
        bits += 1
    D >>= 1 #drop off the smallest number
print 2 ** bits

この場合、16が出力されます

于 2012-05-01T17:17:30.537 に答える