Sprawdź, czy liczba jest podzielna przez 3

Bieżące odpowiedzi skupiają się na cyfrach dziesiętnych, gdy zastosujesz "dodaj wszystkie cyfry i sprawdź, czy dzieli się przez 3". Ta sztuczka działa również w hex; np. 0x12 można podzielić przez 3, ponieważ 0x1 + 0x2 = 0x3. A "konwersja" na hex jest o wiele łatwiejsza niż konwersja na dziesiętne.

Pseudo-kod:

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;
}

[edytuj] Zainspirowany R, szybsza wersja (o log 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;
}

Podziel liczbę na cyfry. Dodaj cyfry razem. Powtarzaj, aż zostanie Ci tylko jedna cyfra. Jeśli cyfra wynosi 3, 6 lub 9, liczba jest podzielna przez 3. (I nie zapomnij obsłużyć 0 jako specjalnego przypadku).

Podczas gdy technika konwersji na ciąg znaków, a następnie dodawania cyfr dziesiętnych razem jest elegancka, to albo wymaga podziału, albo jest nieefektywna w kroku konwersji na ciąg znaków. Czy istnieje sposób na zastosowanie idei bezpośrednio do liczby binarnej, bez uprzedniej konwersji na ciąg cyfr dziesiętnych?

Okazuje się, że jest:

Biorąc pod uwagę liczbę binarną, suma jej nieparzystych bitów minus suma jej parzystych bitów jest podzielna przez 3 iff liczba pierwotna była podzielna przez 3.

Jako przykład: weźmy liczbę 3726, która jest podzielna przez 3. W systemie binarnym jest to 111010001110. Więc bierzemy cyfry nieparzyste, zaczynając od prawej i przesuwając się w lewo, które są [1, 1, 0, 1, 1, 1]; suma tych 5. Parzyste bity to [0, 1, 0, 0, 0, 1]; suma tych 2. 5-2 = 3, z czego możemy wnioskować, że liczba pierwotna jest podzielna przez 3.

Liczba podzielna przez 3, iirc ma cechę, że suma jej cyfry jest podzielna przez 3. Na przykład,

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

W pytaniu wywiadu zasadniczo prosi Cię o wymyślenie (lub już znasz) zasady podzielności z 3 jako dzielnikiem.

Jedna z reguł podzielności dla 3 jest następująca:

Weź dowolną liczbę i dodaj do siebie każdą cyfrę w liczbie. Następnie weź tę sumę i określ, czy jest podzielna przez 3 (powtarzając tę samą procedurę w razie potrzeby). Jeśli liczba końcowa jest podzielna przez 3, to liczba pierwotna jest podzielna przez 3.

Przykład:

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.

Zobacz też

• Wikipedia / zasada podzielności - ma wiele reguł dla wielu dzielników

Podano liczbę x. Konwertuj x na ciąg znaków. Analizuje łańcuch znaków po znaku. Konwertuje każdy przetworzony znak na liczbę (używając atoi ()) i sumuje wszystkie te liczby w nową liczbę y. Powtórz proces, aż twój końcowy numer wynikowy będzie miał jedną cyfrę. Jeśli ta jedna cyfra jest równa 3,6 lub 9, to oryginalna liczba x jest podzielna przez 3.

Moje rozwiązanie w Javie działa tylko dla 32-bitowych unsigned 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;
}

Najpierw zmniejsza liczbę do liczby mniejszej niż 32. Ostatni krok sprawdza podzielność, przesuwając maskę odpowiednią liczbę razy w prawo.

Nie napisałeś tego C, ale skoro wspomniałeś atoi, to podam rozwiązanie C:

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

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
*/
}

Stosując tę samą zasadę, aby uzyskać wynik testu podzielności przez "n", możemy : pomnóż liczbę przez 0x1 0000 0000 - (1 / n)*0xFFFFFFFF compare to ( 1 / n) * 0xFFFFFFFF

Odpowiednikiem jest to, że dla niektórych wartości test nie będzie w stanie zwrócić poprawnego wyniku dla wszystkich 32-bitowych liczb, które chcesz przetestować, na przykład z podzielnością przez 7:

Mamy 0x100000000 - (1/n)*0xffffffff = 0xDB6DB6DC oraz 7 * 0xDB6DB6DC = 0x6 0000 0004, Przetestujemy tylko jedną czwartą wartości, ale z pewnością możemy tego uniknąć dzięki odejmowaniu.

Inne przykłady:

11 * 0xE8BA2E8C = A0000 0004, jedna czwarta wartości

17 * 0xF0F0F0F1 = 10 0000 0000 1 w porównaniu do 0xf0f0f0f Każda wartość !

Itd., możemy nawet przetestować każdą liczbę łącząc liczby naturalne między nimi.

Liczba jest podzielna przez 3, jeśli wszystkie cyfry w liczbie po dodaniu dają wynik 3, 6 lub 9. Na przykład 3693 jest podzielne przez 3 jako 3+6+9+3 = 21 i 2+1=3 i 3 jest podzielne przez 3.

Liczba jest podzielna przez 3, jeśli suma cyfr liczby jest podzielna przez 3. możesz więc pobrać każdą cyfrę jako podłańcuch wprowadzanej liczby, a następnie dodać je. następnie powtarzasz ten proces, dopóki nie będzie tylko jednocyfrowego wyniku.

Jeśli jest to 3, 6 lub 9 liczba jest dzielona przez 3.

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;
}

Na niektórych kompilatorach jest to jeszcze szybsze niż zwykły sposób: x % 3. Czytaj więcej TUTAJ .

C # rozwiązanie do sprawdzania, czy liczba jest dzielona przez 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();

        }

    }
}

Oto twoje zoptymalizowane rozwiązanie, które każdy powinien znać.................

Źródło: http://www.geeksforgeeks.org/archives/511

Program:

#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;
}

Liczba jest podzielna przez 3 iff suma jej cyfr jest podzielna przez 3. Możesz używać tej definicji rekurencyjnie, dopóki nie zostanie Ci jedna cyfra. Jeśli wynikiem jest 3, 6 lub 9, pierwotna liczba jest podzielna przez 3, w przeciwnym razie nie jest.

Exaple: 33333 => 15 (3+3+3+3+3) => 6 (1+5) zatem 33333 jest podzielne przez 3.

Zobacz Zasady podzielności

Oto pseudo-algol, który wymyśliłem .

Śledźmy postęp binarny wielokrotności 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

Wystarczy zauważyć, że dla wielokrotności binarnej 3 x=abcdef w następujących parach abc=(000,011),(001,100),(010,101) cde należy zmienić, stąd mój zaproponowany algorytm :

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