Critério de divisibilidade por 3

Os critérios de divisibilidade são regras simples que permitem verificar se um determinado número inteiro A é divisível por um inteiro B baseado em propriedades da sua representação.

Os critérios de divisibilidade podem ser utilizados para realizar de testes de validade para cálculos de somas, subtrações e multiplicações.

Critério de divisibilidade de 3 na base 10

Para desenvolver a regra de divisibilidade por 3, vamos considerar um número n com 4 dígitos na notação decimal abcd.

Logo, um número é divisível por 3, se somente se, a soma dos seus dígitos decimais é divisível por 3.

int sum_dig(int n){
  int s=0;
  while(n>0){
    s = s + n%10;
    n=n/10;
  }
  return s;
}
int mod3(int n){
  while( n >= 10){
    printf("%d = ",n);
    n = sum_dig(n);
    printf("%d mod 3\n",n);
  }
  printf("%d = %d mod 3\n",n,n%3);
  return  n%3;
}
int main(){
  int n;
  while( scanf("%d",&n) && n > 0){
    mod3(n);
  }
}
Saída 

254245
254245 = 22 mod 3
22 = 4 mod 3
4 = 1 mod 3

Critério de divisibilidade na base 2

Vamos desenvolver agora o critério de divisibilidade por 3 na base 2, vamos considerar um número n  com 4 dígitos na notação binária abcd.

Logo, um número é divisível por 3 na base 2, se somente se, a soma dos dígitos binários das posições pares menos os dígitos da posição ímpar é divisível por 3.
Para n < 0, podemos desenvolver a seguinte critério de divisibilidade por 3.

Logo, um número negativo é divisível por 3 na base 2, se somente se, a soma dos dígitos binários das posições ímpares menos os dígitos binários das posições pares é divisível por 3.


Problema 1 Pegar os dígitos nas posições pares.
Em cada byte, precisamos extrair os seguintes bits 01010101 = 55 (hexadecimal).

#define EVEN(n) n & 0x55555555

Problema 2 Pegar os dígitos nas posições ímpares.

Em cada byte, precisamos extrair os seguintes bits 10101010 = aa (hexadecimal).

#define ODD(n) n &  0xaaaaaaaa

Problema 3 Contar os bits ligados um número inteiro. 

Solução 1: 
int count_bits1(int num){
  int count = 0;
  while(num){
    count += num & 1;
    num >>=1;
  }
  return count;
}


Complexidade O(lg N)



Solução 2
int count_bits2(int num)
{
    int count = 0;
    while(num)
    {
          num = num & (num - 1);
          count++;
    }
    return count;
}


Complexidade O(k) k é o número de bits ligados

Solução 3 Construindo uma tabela, em tempo de compilação usando metaprogramação, 

que conta todos os bits ligados em todos os números que podem ser representados 

por 1 byte.

   

Número
   

Binário
   

BitsSetTable256
  
   

0
   

00000000
   

0
  
   

1
   

00000001
   

1
  
   

2
   

00000010
   

1
  
   

3
   

00000011
   

2
  

static const unsigned char BitsSetTable256[256] =
{
# define B2(n) n, n+1, n+1, n+2
# define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
# define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
B6(0), B6(1), B6(1), B6(2)
};
int count_bits3(int num){
  return BitsSetTable256[num & 0xff] +   

BitsSetTable256[(num >> 8) & 0xff] +   

BitsSetTable256[(num >> 16) & 0xff] +   

BitsSetTable256[num >> 24]; 

}

Algoritmo Final

int mod3(int n){
  while(n>=2 || n <= -2){
    printf("%d = ",n);
    if(n>0){
      n = count_bits3(EVEN(n)) - count_bits3(ODD(n));
    }else{
      //Magnitude de um n�mero negativo
      n = ~n + 1; //complemento de 2 + 1
      n = count_bits3(ODD(n)) - count_bits3(EVEN(n));
    }
    printf("%d mod 2\n",n);  
  }
  if(n<0) { printf("%d = %d mod 2\n",n,n+3); n = n+3; }
  return n;
} 
int main(){
  int n;
  while( scanf("%d",&n) && n > 0){
    mod3(n);
  }
  system("PAUSE");
}

Saída

254245

254245 = 1 mod 3