Exercício resolvido – otimizando soluções

Inicio com um exercício de algoritmos bastante tradicional e simples. O exercício consiste em determinar se um número é par ou ímpar.

Para resolver, o algoritmo abaixo foi o primeiro que desenvolvi e possivelmente é a solução que seria, de maneira similar, desenvolvida pela maioria das pessoas. Na solução é testado se o valor resultante da sobra da divisão do número por dois é igual a zero, ou seja, verificado se o número é divisível por 2.

#include <stdio.h>

int main() {
    int x = 18;

    if (x%2 == 1) {
        printf("Impar");
    } else {
        printf("Par");
    }

    return 0;
}

Uma forma otimizada para resolver esse problema é utilizar o operador bitwise AND. O código a seguir mostra a solução utilizando esse operador e é bastante parecido com o anterior, apenas alterando a condição de teste na linha 6.

A solução utilizando o bitwise uma solução mais sofisticada, mas mais eficiente. Logicamente é necessário entender sobre o operador bitwise AND, o que pode ser visto em http://www.galirows.com.br/meublog/programacao/operadores-bitwise-cpp/. Como em binários, o número 1 = 00000001, e operador somente resulta em 1 se dos dois bits comparados forem o valor 1, somente um número com o último bit 1 é que resultaria o teste em verdadeiro e com isso sabemos que o número é ímpar.

#include <stdio.h>

int main() {
    int x = 18;

    if (x & 1) {
        printf("Impar");
    } else {
        printf("Par");
    }

    return 0;
}

Claramente a solução utiliza um conhecimento adicional da linguagem C com a manipulação de bits, mas de que maneira isso torna a solução mais eficiente? a operação com bits costuma ser mais rápida do que as operações aritméticas e relacionais. A diferença é bem pequena e para testar é preciso realizar as operações muitas vezes. No código abaixo os cálculos são feitos várias vezes. Utilizando o cálculo da linha 6 do código abaixo o tempo médio das execuções que executei ficaram em torno de 4,6 segundos, enquanto utilizando o cálculo da linha 5 o tempo foi de 4,7 segundos.

É pouca diferença? sim. Ainda mais considerando que a operação dificilmente seria realizada tantas vezes em uma solução. Então não existe problema algum em utilizar a solução tradicional, mas é interessante conhecer a alternativa com o bitwise.

#include <stdio.h>

int main() {
    for (int i=0; i < 2147483647; i++)
        (i % 2 == 1);
        //(i & 1);

    return 0;
}

Veja que solicitei para o laço for executar 2.147.483.647 vezes e que esse é o valor máximo que uma variável int pode assumir.

Dado um conjunto de números onde todos os elementos ocorrem um número par de vezes, exceto um desses valores, encontre o número que ocorre um número ímpar de vezes.

Para resolver, o algoritmo abaixo foi o primeiro que desenvolvi. Na função principal é criado o vetor com alguns valores e chamada a função acharImpar(). Essa função cria uma matriz com duas colunas na qual em cada linha serão armazenados cada valor encontrado do vetor e na coluna correspondente o número de vezes que o valor foi encontrado. O número de linhas da matriz considerou o maior tamanho dessa matriz: se todos os valores formarem um par + um número sem par. No caso do meu vetor definido na função main(), a matriz terá 9/2+1=5 linhas (lembre-se que 9/2=4, uma vez que int/int resulta apenas na parte inteira da divisão), embora apenas 4 serão realmente utilizadas.

O algoritmo se baseia em adicionar na matriz cada novo número encontrado no vetor e contar quantas vezes cada um deles ocorre. Ao final é buscado qual das contagens de ocorrência resulta em um valor ímpar e o valor correspondente é retornado.

#include <stdio.h>

int acharImpar(int arr[], int n) {
    int i, j, qtd=0, mat[n/2+1][2];

    for (i=0; i < n; i++) {
        //verifica se o valor já está na matriz
        for (j=0; j < qtd; j++) {
            if (mat[j][0] == arr[i]) {
                mat[j][1]++;
                j = n;
                break;
            }
        }
        //adiciona novo valor na matriz
        if (j != n) {
            mat[qtd][0] = arr[i];
            mat[qtd][1] = 1;
            qtd++;
        }
    }

    //mostra a matriz
    for (i=0; i < qtd; i++) {
        printf("%i: %i \n", mat[i][0], mat[i][1]);
    }

    //retorna a ocorrência ímpar
    for (i=0; i < qtd; i++) {
        if (mat[i][1]%2 == 1) {
            return mat[i][0];
        }
    }
}

int main(void) {
    int arr[] = { 10, 10, 11, 11, 11, 20, 12, 11, 12 };
    int n = sizeof(arr) / sizeof(arr[0]); //calcula o tamanho do vetor
    printf("O valor que aparece um numero impar de vezes eh: %d ", acharImpar(arr, n));
    return 0;
}

Agora apresento uma solução que utiliza uma operação bitwise. O código abaixo para a função acharImpar() utiliza o bitwise XOR e obtém o mesmo resultado da versão anterior. É uma solução mais sofisticada com certeza, mas mais econômica na alocação de memória pois dispensa a utilização da matriz.

int acharImpar(int arr[], int n) {
    int res = 0, i;
    for (i = 0; i < n; i++)
        res ^= arr[i];
        //printf("%d: %d \n", arr[i], res);
    return res;
}

Para entender o que ocorre nesse código, considere o que seria mostrado com o printf da linha 5. O resultado é mostrado abaixo. Veja que a cada interação ocorrer uma soma e depois uma subtração do valor do array. Assim, cada par de valor acaba se anulando, mesmo que não estejam consecutivamente, e fica sobrando apenas o valor que não tinha um par.

10: 10
10: 0
11: 11
11: 0
11: 11
20: 31
12: 19
11: 24
12: 20

Veja que nessa solução foi utilizado o princípio do operador XOR, que funciona identificando um elemento que ocorre exclusivamente.

Espero ter ajudado a entender um pouco mais sobre os operadores bitwise. Até uma próxima.