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

Question

Мне нужно выяснить, делится ли число на 3 без использования %, / или *. Подсказка заключалась в использовании функции atoi(). Есть идеи как это сделать?

Answer 1

Все текущие ответы фокусируются на десятичных цифрах, когда применяется «добавить все цифры и посмотреть, делится ли это на 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 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 2

Вычитайте 3 до тех пор, пока вы либо

а) не нажмете 0 - число делится на 3

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

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

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

Вопрос об интервью, по сути, просит вас придумать (или уже знали) сокращение правила делимости с делителем 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.

Смотри также

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

Answer 6

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

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

Answer 7

Мое решение в Java работает только для 32-битных без знака int с.

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. Последний шаг проверяет делимость, сдвигая маску на соответствующее количество раз вправо.

Answer 8

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

Answer 9

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 Каждые значения!

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

Answer 10

Вы не пометили этот C, но так как вы упомянули atoi, я собираюсь дать решение C:

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