Verifique se um número é divisível por 3

Question

Preciso descobrir se um número é divisível por 3 sem usar %, / ou *. A dica dada foi para usar atoi() função. Alguma ideia de como fazer isso?

Answer 1

Subtraia 3 até você também

a) Hit 0 - o número foi divisível por 3

b) Obtenha um número menor que 0 - o número não foi divisível

- Versão editada para corrigir problemas notáveis

while n > 0:
    n -= 3
while n < 0:
    n += 3
return n == 0

Answer 2

Todas as respostas atuais se concentram em dígitos decimais, ao aplicar o "Adicione todos os dígitos e veja se isso se divide por 3". Esse truque realmente funciona em hexadecimal também; Por exemplo, 0x12 pode ser dividido por 3 porque 0x1 + 0x2 = 0x3. E "converter" em hexadecimal é muito mais fácil do que converter em decimal.

Pseudo-código:

int reduce(int i) {
  if (i > 0x10)
    return reduce((i >> 4) + (i & 0x0F)); // Reduces 0x102 to 0x12 to 0x3.
  else
   return i; // Done.
}
bool isDiv3(int i) {
  i = reduce(i);
  return i==0 || i==3 || i==6 || i==9 || i==0xC || i == 0xF;
}

Editar] Inspirado por R, uma versão mais rápida (o log n):

int reduce(unsigned i) {
  if (i >= 6)
    return reduce((i >> 2) + (i & 0x03));
  else
   return i; // Done.
}
bool isDiv3(unsigned  i) {
  // Do a few big shifts first before recursing.
  i = (i >> 16) + (i & 0xFFFF);
  i = (i >> 8) + (i & 0xFF);
  i = (i >> 4) + (i & 0xF);
  // Because of additive overflow, it's possible that i > 0x10 here. No big deal.
  i = reduce(i);
  return i==0 || i==3;
}

Answer 3

Divida o número em dígitos. Adicione os dígitos. Repita até que você tenha apenas um dígito restante. Se esse dígito for 3, 6 ou 9, o número será divisível por 3. (e não se esqueça de lidar com 0 como um caso especial).

Answer 4

Embora a técnica de conversão para uma corda e, em seguida, adicionar os dígitos decimais seja elegante, ela requer divisão ou é ineficiente na etapa de conversão em uma corda. Existe uma maneira de aplicar a idéia diretamente a um número binário, sem primeiro converter para uma série de dígitos decimais?

Acontece que existe:

Dado um número binário, a soma de seus bits ímpares menos a soma de seus bits pares é divisível por 3 se o número original foi divisível por 3.

Como exemplo: pegue o número 3726, que é divisível em 3. Em binário, este é 111010001110. Por isso, pegamos os dígitos estranhos, começando da direita e movendo -se para a esquerda, que são [1, 1, 0, 1, 1, 1]; a soma destes é 5. Os bits pares são [0, 1, 0, 0, 0, 1]; a soma destes é 2. 5 - 2 = 3, do qual podemos concluir que o número original é divisível por 3.

Answer 5

Um número divisível por 3, o IIRC tem uma característica de que a soma de seu dígito seja divisível por 3. por exemplo,

12 -> 1 + 2 = 3
144 -> 1 + 4 + 4 = 9

Answer 6

A pergunta da entrevista pede essencialmente que você encontre (ou já conheceu) a regra de divisibilidade abreviação com 3 como divisor.

Uma das regra de divisibilidade para 3 é a seguinte:

Pegue qualquer número e adicione cada dígito no número. Em seguida, pegue essa soma e determine se é divisível por 3 (repetindo o mesmo procedimento necessário). Se o número final for divisível por 3, o número original será divisível por 3.

Exemplo:

16,499,205,854,376
=> 1+6+4+9+9+2+0+5+8+5+4+3+7+6 sums to 69
=> 6 + 9 = 15 => 1 + 5 = 6, which is clearly divisible by 3.

Veja também

• Regra da Wikipedia/divisibilidade - tem muitas regras para muitos divisores

Answer 7

Dado um número x. Converter x em uma string. Analise o caractere da string por caractere. Converta cada caractere analisado em um número (usando Atoi ()) e adicione todos esses números em um novo número y. Repita o processo até que seu número resultante final tenha um dígito de comprimento. Se esse dígito for 3,6 ou 9, o número original x é divisível por 3.

Answer 8

Minha solução em Java funciona apenas por 32 bits não assinado ints.

static boolean isDivisibleBy3(int n) {
  int x = n;
  x = (x >>> 16) + (x & 0xffff); // max 0x0001fffe
  x = (x >>> 8) + (x & 0x00ff); // max 0x02fd
  x = (x >>> 4) + (x & 0x000f); // max 0x003d (for 0x02ef)
  x = (x >>> 4) + (x & 0x000f); // max 0x0011 (for 0x002f)
  return ((011111111111 >> x) & 1) != 0;
}

Primeiro reduz o número para um número menor que 32. A última etapa verifica a divisibilidade, mudando a máscara o número apropriado de vezes para a direita.

Answer 9

Você não marcou este C, mas desde que você mencionou atoi, Vou dar uma solução C:

int isdiv3(int x)
{
    div_t d = div(x, 3);
    return !d.rem;
}

Answer 10

bool isDiv3(unsigned int n)
{
    unsigned int n_div_3 =
        n * (unsigned int) 0xaaaaaaab;
    return (n_div_3 < 0x55555556);//<=>n_div_3 <= 0x55555555

/*
because 3 * 0xaaaaaaab == 0x200000001 and
 (uint32_t) 0x200000001 == 1
*/
}

bool isDiv5(unsigned int n)
{
    unsigned int n_div_5 =
        i * (unsigned int) 0xcccccccd;
    return (n_div_5 < 0x33333334);//<=>n_div_5 <= 0x33333333

/*
because 5 * 0xcccccccd == 0x4 0000 0001 and
 (uint32_t) 0x400000001 == 1
*/
}

Seguindo a mesma regra, para obter o resultado do teste de divisibilidade por 'n', podemos: Multiplicar o número por 0x1 0000 0000 - (1/n) * 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff.

A contraparte é que, para alguns valores, o teste não poderá retornar um resultado correto para todos os números de 32 bits que você deseja testar, por exemplo, com divisibilidade por 7:

Obtivemos 0x100000000- (1/n) * 0xfffffffffff = 0xdb6db6dc e 7 * 0xdb6db6dc = 0x6 0000 0004, testaremos apenas um quarto dos valores, mas certamente podemos evitar isso com substrações.

Outros exemplos:

11 * 0xe8ba2e8c = a0000 0004, um quarto dos valores

17 * 0xf0f0f0f1 = 10 0000 0000 1 Comparando com 0xf0f0f todos os valores!

Etc., podemos até testar todos os números combinando números naturais entre eles.

Answer 11

Um número é divisível por 3 se todos os dígitos do número quando adicionados fornecerem um resultado 3, 6 ou 9. Por exemplo, 3693 for divisível por 3 como 3+6+9+3 = 21 e 2+1 = 3 e 3 é divisível por 3.

Answer 12

inline bool divisible3(uint32_t x)  //inline is not a must, because latest compilers always optimize it as inline.
{
    //1431655765 = (2^32 - 1) / 3
    //2863311531 = (2^32) - 1431655765
    return x * 2863311531u <= 1431655765u;
}

Em alguns compiladores, isso é ainda mais rápido do que a maneira regular: x % 3. Consulte Mais informação aqui.

Answer 13

Bem, um número é divisível por 3 se toda a soma dos dígitos do número for divisível por 3. para que você possa obter cada dígito como uma substring do número de entrada e depois adicione -os. Você repetiria esse processo até que haja apenas um resultado de um dígito.

Se isso for 3, 6 ou 9, o número será divisível em 3.

Answer 14

Um número é divisível por 3 se a soma de seus dígitos é divisível por 3. Você pode usar essa definição recursivamente até ficar com um único dígito. Se o resultado for 3, 6 ou 9, o número original será divisível por 3, caso contrário, não será.

Exaple: 33333 => 15 (3+3+3+3+3) => 6 (1+5) SO 33333 é divisível por 3.

Ver Regras de divisibilidade

Answer 15

C# Solução para verificar se um número for divisível por 3

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int num = 33;
            bool flag = false;

            while (true)
            {
                num = num - 7;
                if (num == 0)
                {
                    flag = true;
                    break;
                }
                else if (num < 0)
                {
                    break;
                }
                else
                {
                    flag = false;
                }
            }

            if (flag)
                Console.WriteLine("Divisible by 3");
            else
                Console.WriteLine("Not Divisible by 3");

            Console.ReadLine();

        }
    }
}

Answer 16

• Aqui está um pseudo-algol que eu inventei.

Vamos seguir o progresso binário de múltiplos de 3

000 011
000 110

001 001
001 100
001 111

010 010
010 101


011 000
011 011
011 110

100 001
100 100
100 111

101 010
101 101

Apenas tenha uma observação de que, para um múltiplo binário de 3 x = abcdef nos seguintes casais abc=(000,011),(001,100),(010,101) CDE mudança de mudança, portanto, minha proposta algoritmo:

divisible(x):

    y = x&7

    z = x>>3

    if number_of_bits(z)<4

        if z=000 or 011 or 110 , return (y==000 or 011 or 110) end

        if z=001 or 100 or 111 , return (y==001 or 100 or 111) end

        if z=010 or 101 , return (y==010 or 101) end

    end

    if divisible(z) , return (y==000 or 011 or 110) end

    if divisible(z-1) , return (y==001 or 100 or 111) end

    if divisible(z-2) , return (y==010 or 101) end

end

Answer 17

Aqui está a sua solução otimizada que todos devem saber .................

Fonte: http://www.geeksforgeeks.org/archives/511

#include<stdio.h>


int isMultiple(int n)
{
    int o_count = 0;
    int e_count = 0;


    if(n < 0)  
           n = -n;
    if(n == 0) 
           return 1;
    if(n == 1)
           return 0;

    while(n)
    {

        if(n & 1)
           o_count++;
        n = n>>1;


        if(n & 1)
            e_count++;
        n = n>>1;
    }

     return isMultiple(abs(o_count - e_count));
}


int main()
{
    int num = 23;
    if (isMultiple(num))
        printf("multiple of 3");
    else
        printf(" not multiple of 3");

    return 0;
}