2

線形時間の複雑さでビット単位の OR 合計または配列を見つけるアルゴリズムはありますか?

配列が {1,2,3} の場合、すべてのペアの合計 ID は 1|2 + 2|3 + 1|3 = 9 とします。

次のアルゴリズムを使用して、O(n) 内のすべてのペア AND 合計を見つけることができます。これを変更して、すべてのペア OR 合計を取得するにはどうすればよいですか。

int ans = 0;  // Initialize result

// Traverse over all bits
for (int i = 0; i < 32; i++)
{
    // Count number of elements with i'th bit set
    int k = 0;  // Initialize the count
    for (int j = 0; j < n; j++)
        if ( (arr[j] & (1 << i)) )
            k++;

    // There are k set bits, means k(k-1)/2 pairs.
    // Every pair adds 2^i to the answer. Therefore,
    // we add "2^i * [k*(k-1)/2]" to the answer.
    ans += (1<<i) * (k*(k-1)/2);
}

ここから: http://www.geeksforgeeks.org/calculate-sum-of-bitwise-and-of-all-pairs/

4

1 に答える 1

6

線形時間で実行できます。考え方は次のとおりです。

  1. 各ビット位置について、そのビットが 1 に設定されている配列内のエントリの数を記録します。この例では、1 のビットが設定された 2 つのエントリ (1 と 3) と、2 のビットが設定された 2 つのエントリ (2および 3)。

  2. 数値ごとに、各ビットを個別に調べ、キャッシュされた合計を使用して、配列内の他のすべての数値との数値のビットごとの OR の合計を計算します。たとえば、合計 1|1 + 1|2 + 1|3 = 1 + 3 + 3 = 7 を考えてみましょう。

    1 の最後のビットは 1 であるため、bitwise または with 1 の結果の最後のビットは 1 に設定されます。したがって、3 つの数値 1|1、1|2、および 1|3 の最後のビットはすべて 1 になります。 . これらの数値のうちの 2 つは 2 のビットが 1 に設定されています. これは正確には 2 のビットが 1 に設定されている要素の数です. ビットをグループ化することにより, 合計 3*1 (3 つの 1 のビット) + 2 を得ることができます. *2 (2 のビットが 2 つ) = 7。

  3. 要素ごとにこの手順を繰り返すと、配列内の要素の順序付けられたすべてのペアについて、すべてのビットごとの OR の合計を計算できます。したがって、あなたの例では、1|2 と 2|1 が計算され、1|1 も計算されます。したがって、1|1 のようにすべてのケースを差し引いてから、2 で割って二重カウントを考慮する必要があります。

あなたの例でこのアルゴリズムを試してみましょう。

  1. 数字を 2 進数で書くと、{1,2,3} = {01, 10, 11} になります。1 のビットが設定された 2 つの数字と、2 のビットが設定された 2 つの数字があります。

  2. 01 の場合、ors の合計は 3*1 + 2*2 = 7 になります。

  3. 10 の場合、or の合計は 2*1 + 3*2 = 8 になります。
  4. 11 の場合、or の合計は 3*1 + 3*2 = 9 になります。
  5. これらを合計すると、7+8+9 = 24 になります。1|1 = 1、2|2 = 2、および 3|3 = 3 を差し引く必要があります。これらを合計に数えたからです。24-1-2-3 = 18.
  6. 最後に、1|3 のようなものを 2 回数えたので、2 で割る必要があります。18/2 = 9、正しい合計です。

このアルゴリズムは O(n * 任意の配列要素の最大ビット数) です。

編集:すべてのペアからすべての 0-0 ペアのカウントを単純に減算して、各ビット位置のすべての 0-1 または 1-1 ペアを取得することで、投稿されたアルゴリズムを変更できます。そのようです：

int ans = 0;  // Initialize result

// Traverse over all bits
for (int i = 0; i < 32; i++)
{
    // Count number of elements with i'th bit not set
    int k = 0;  // Initialize the count
    for (int j = 0; j < n; j++)
        if ( !(arr[j] & (1 << i)) )
            k++;

    // There are k not set bits, means k(k-1)/2 pairs that don't contribute to the total sum, out of n*(n-1)/2 pairs.
    // So we subtract the ones from don't contribute from the ones that do.

    ans += (1<<i) * (n*(n-1)/2 - k*(k-1)/2);
}
于 2016-08-25T17:36:44.833 に答える