Soma a diferença de bits entre todos os pares de números em uma coleção

Existem muitas maneiras de comparar dois inteiros. Um deles é comparar cada bit de número, por exemplo, comparando 2 e 1:

2 -> ...0010
1 -> ...0001

Os dois últimos bits são diferentes, então o resultado é 2. Aqui está uma das muitas implementações possíveis:

public static int bitDiff(int a, int b)
{
    int count = 0;
    for (int i = 0; i < 32; i++)
    {
        int aBit = (1 << i) & a;
        int bBit = (1 << i) & b;
        if (aBit != bBit)
        {
            count++;
        }
    }
    return count;
}

Agora vamos dar uma olhada em um problema mais complexo. A partir de uma coleção de inteiros, calcule bitDiff de todos os pares e some os resultados.

∑ bitDiff (array [i], array [j])

input: {1,2,3} -> pairs {(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)} -> output: 8

Isso pode ser otimizado gerando apenas metade dos pares (a operação bitDiff é transitiva), mas ainda é O (n ^ 2). Podemos fazer O (n)? Role para ver uma dica!

<br/> <br/> <br/> <br/> <br/>
<br/> <br/> <br/> <br/> <br/>
<br/> <br/> <br /> <br/> <br/>

E se tivermos apenas 0 e 1 na matriz?

<br/> <br/> <br/> <br/> <br/>
<br/> <br/> <br/> <br/> <br/>
<br/> <br/> <br /> <br/> <br/>

Vamos considerar um caso simples

[0,1] ->  1
[1,1] ->  0
[0,0] ->  0
[1,0] ->  1

Claramente, o resultado é 1 para pares diferentes. Podemos contar 1s e 0s e multiplicar uns aos outros para obter o número de pares cujo resultado é 1 e depois multiplicar por 2 (permutação de um par)

[0,1] = 1 * 1 * 2 = 2
[0,1,1] = 1 * 2 * 2 = 4
[0,1,0,1] = 2 * 2 * 2 = 8

Como obter a generalização para ints?

Podemos ameaçar números como 32 matrizes de 1 e 0

public static bool isBitSet(int number, int index)
{
    int bit = (1 << index) & number;
    return bit > 0;
}

public static int sumPairBitDiff(int[] numbers)
{
    int sum = 0;
    for (int i = 0; i < 32; i++)
    {
        int oneCount = 0;
        int zeroCount = 0;
        foreach (var num in numbers)
        {
            if (isBitSet(num, i)) oneCount++;
        }
        zeroCount = numbers.Length - oneCount;
        sum += oneCount * zeroCount * 2;
    }
    return sum;
}

Impressionante!