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 Respostas
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 ) {
Quandoa
for falso (zero), está concluída a função;odd ^= a & 1;
Aqui estamos fazendo um XOR entre a variávelodd
e o último bit dea
- 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 dea
, 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:
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
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));
}
}
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...
char
armazena 1 byte (8 bits), você está usando o termo errado na sua pergunta.