3

Estou tendo problemas em criar uma funçao que retorna 0 caso o numero de bits setados em um unsigned char for par e 1 se for impar

3
  • 3
    Coloque seu código pra gente ver como está. E informe qual é o problema específico.
    – Maniero
    Commented 23/04/2016 às 21:54
  • O char armazena 1 byte (8 bits), você está usando o termo errado na sua pergunta. Commented 23/04/2016 às 22:19
  • se voce quer perguntar algo sobre seu codigo, poste ele.
    – jsbueno
    Commented 25/04/2016 às 13:39

3 Respostas 3

4

Isso é uma tarefa adequada para operadores de bit:

#include <stdio.h>

int checkParity(unsigned char a) {
    int odd = 0;
    while( a ) {
        odd ^= a & 1;
        a >>= 1;
    }    
    return odd;
}

// teste, igual o do @user5978    
int main(void) {
    int i = 0;
    for (i=0; i<255;i++) {
        printf(" %d => %d\r\n",i,checkParity( i ) );
    }
    return 0;
}

Veja funcionando no IDEONE.

Pontos de interesse:

  • while( a ) { Quando a for falso (zero), está concluída a função;

  • odd ^= a & 1; Aqui estamos fazendo um XOR entre a variável odd e o último bit de a - em outras palavras, se o bit for zero, nada muda, se o bit for um, odd alterna entre 0 e 1.

  • a >>= 1; como já usamos o último bit de a, deslocamos todos os bits para a direita para repetir o processo (o efeito é o mesmo que uma divisão por dois feita com inteiro, só que sem preocupação "matemática").

Basicamente como a pergunta pede zero em caso de bits pares, a lógica é bem simples: a cada bit "ligamos" a variável odd, e no seguinte desligamos. Se a quantidade for par, odd terminará em zero, senão, em um.


Eliminando uma variável:

Uma vez entendido o código acima, ele pode ser simplificado com a remoção da variável odd:

int checkParity(unsigned char a) {
    while( a > 1 ) a = ( a >> 1 ) ^ ( a & 1 );
    return a;
}

É a mesma lógica, mas estamos trabalhando com a rotação sucessiva de a e um XOR com seu último bit.

Veja funcionando no IDEONE.


Solução sem loop:

Esta solução é "inspirada" na postagem do @JJoao, que elimina a necessidade de loop, otimizando mais ainda o resultado. A técnica é diferente, mas a filosofia de "escovar bits" para otimização extrema é parecida.

Parti deste link, que tem uns algoritmos bem interessantes, com operação de bits:

http://www.graphics.stanford.edu/~seander/bithacks.html

Um deles cai como uma luva se adaptado para o nosso caso:

int checkParity(unsigned char a) {
    a ^= a >> 4;
    a &= 0xf;
    return ( 0x6996 >> a ) & 1;
}

Não vou entrar em detalhes da matemática da coisa, mas "desenhando" os bits no papel fica mais fácil de visualizar a "jogada".

Resumindo bastante, como a paridade é cíclica (com inversão), simplesmente o valor é mesclado pra caber em 4 bits, e o valor 0x6996 é simplesmente uma "tabela" com o resultado para os 16 casos possíveis do resultado. É um valor pré-calculado, para otimizar a função.

Veja funcionando no IDEONE

1
  • Cool! gostei: +1
    – JJoao
    Commented 24/04/2016 às 9:48
3

Basta decompor o número fazendo sucessivas divisões por 2, e verificar o resultado da divisão. Dessa forma:

#include <stdio.h>


int check(unsigned char a) {

    int n = 0;

    while (a > 0) {

        if (a%2!=0) {
            n++;
        }

        a = a/2;

    }    
     return !(n%2==0);
}


int main()
{
   int i = 0;

    for (i=0; i<255;i++) {
        printf(" %d => %d\r\n",i,check(i));
    } 

}
3

Seja x composto por 8 bits x=(a b c d e f g h)

Paridade(x) = xor( a b c d e f g h )

O operador xor em C é ^.

int check(unsigned char x) {

  x ^= x >> 4;        // x = abcdefgh xor 0000abcd = a b c d ae bf cg dh
  x ^= x >> 2;        // x = ... = a b ac bd ace bdf aceg bdfh
  x ^= x >> 1;        // x = ... = a ab abc abcd ... ... abcedfgh
                      // ou seja o bit menos significativo tem a informação pretendida
  return x & 1;       // retorna bit menos significativo (remove os outros bits)
}

(Não é invenção minha: lembro-me vagamente de ter lido algo parecido com isto algures num livro)

Update: alertado pelo precioso comentario de @Baco juntei uma pequena correção (ligada a compatibilização unsign char / int / op bit a bit); vamos ver se é desta...

0

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .