Проверить, делится ли число на 3

Вычтите 3, пока вы не

а) попадание 0 - число делилось на 3

б) получить число меньше 0 - число не делится

-- отредактированная версия для исправления отмеченных проблем

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

Все текущие ответы сосредоточены на десятичных цифрах при применении «добавить все цифры и посмотреть, делится ли это на 3». Этот трюк работает и в шестнадцатеричном формате; например 0x12 можно разделить на 3, потому что 0x1 + 0x2 = 0x3. И «преобразование» в шестнадцатеричное намного проще, чем преобразование в десятичное.

Псевдокод:

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

[править] Вдохновленный R, более быстрая версия (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;
}

Разделите число на цифры. Сложите цифры вместе. Повторяйте, пока у вас не останется только одна цифра. Если эта цифра 3, 6 или 9, число делится на 3. (И не забудьте обработать 0 как особый случай).

Хотя метод преобразования в строку и последующего сложения десятичных цифр элегантен, он либо требует деления, либо неэффективен на этапе преобразования в строку. Есть ли способ применить эту идею непосредственно к двоичному числу без предварительного преобразования в строку десятичных цифр?

Оказывается, есть:

Для двоичного числа сумма его нечетных битов за вычетом суммы его четных битов делится на 3 тогда и только тогда, когда исходное число делилось на 3.

В качестве примера: возьмем число 3726, которое делится на 3. В двоичном формате это 111010001110. Итак, мы берем нечетные цифры, начиная справа и двигаясь влево, то есть [1, 1, 0, 1, 1, 1]; их сумма равна 5. Четные биты равны [0, 1, 0, 0, 0, 1]; их сумма равна 2. 5 - 2 = 3, из чего можно сделать вывод, что исходное число делится на 3.

Число, делящееся на 3, iirc имеет характеристику, состоящую в том, что сумма его цифр делится на 3. Например,

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

Вопрос на собеседовании, по сути, требует, чтобы вы придумали (или уже знали) стенограмму правила делимости с 3 в качестве делителя.

Одно из правил делимости на 3 выглядит следующим образом:

Возьмите любое число и сложите вместе каждую цифру этого числа. Затем возьмите эту сумму и определите, делится ли она на 3 (при необходимости повторяя ту же процедуру). Если конечное число делится на 3, то исходное число делится на 3.

Пример:

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.

Смотрите также

• Википедия/Правило делимости — содержит много правил для многих делителей

Дано число х. Преобразовать x в строку. Разобрать строку символ за символом. Преобразуйте каждый проанализированный символ в число (используя atoi()) и сложите все эти числа в новое число y. Повторяйте процесс, пока ваш окончательный результирующий номер не будет состоять из одной цифры. Если эта цифра равна 3,6 или 9, исходное число x делится на 3.

Мое решение на Java работает только для 32-разрядных неподписанных 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;
}

Сначала он уменьшает число до числа меньше 32. Последний шаг проверяет делимость, сдвигая маску на соответствующее число раз вправо.

Вы не отметили это C, но, поскольку вы упомянули atoi, я собираюсь дать решение 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
*/
}

Следуя тому же правилу, чтобы получить результат проверки делимости на 'n', мы можем: умножить число на 0x1 0000 0000 - (1/n)*0xFFFFFFFF сравнить с (1/n) * 0xFFFFFFFF

Обратной стороной является то, что для некоторых значений тест не сможет вернуть правильный результат для всех 32-битных чисел, которые вы хотите проверить, например, с делимостью на 7:

мы получили 0x100000000- (1/n)*0xFFFFFFFF = 0xDB6DB6DC и 7 * 0xDB6DB6DC = 0x6 0000 0004. Мы проверим только четверть значений, но мы определенно можем избежать этого с помощью вычитаний.

Другие примеры:

11 * 0xE8BA2E8C = A0000 0004, четверть значений

17 * 0xF0F0F0F1 = 10 0000 0000 1 по сравнению с 0xF0F0F0F Все значения !

И т. д., мы даже можем проверить каждое число, комбинируя между ними натуральные числа.

Число делится на 3, если все цифры в числе при сложении дают результат 3, 6 или 9. Например, 3693 делится на 3, так как 3+6+9+3 = 21 и 2+1=3 и 3 делится на 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;
}

В некоторых компиляторах это даже быстрее обычного: x % 3. Подробнее читайте здесь.

ну, число делится на 3, если вся сумма цифр числа делится на 3. Таким образом, вы можете получить каждую цифру как подстроку входного числа, а затем добавить их. затем вы будете повторять этот процесс до тех пор, пока не будет получен только однозначный результат.

если это 3, 6 или 9, то число делится на 3.

• Вот псевдоалгол, который я придумал.

Давайте проследим двоичный прогресс кратных 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

просто обратите внимание, что для двоичного числа, кратного 3, x=abcdef в следующих парах abc=(000,011),(001,100),(010,101) cde< /strong> не меняется, следовательно, мой предложенный алгоритм:

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