Проверка того, делится ли число на 9

Я попытался разработать новый способ проверить, является ли число делимым на 9. Я написал мой код , и он работает нормально. Мне не разрешено использовать *, / и %.

int isDivby9(int x)
{
    int status = 0; 
    int divby8 = 0;

        int orgx = x;
        if(x>=9)
        {
            divby8 = x >> 3;
            int olddivby8 = divby8;
            while(divby8 >= 9)
            {
                divby8 = divby8 - 9;
            }
            if(divby8 == (orgx - (olddivby8 << 3)))
            {
                status = 1;
            }
            else{
                status = 0;
            }
            x = divby8;
        }

    return status;
}

Может кто-нибудь, пожалуйста, проверьте, является ли это хорошим способом проверить, является ли число делимостью на 9? Это слишком сложно? Есть ли лучший способ выполнить то же самое? Я также упомянул логику, приведенную в geeksforgeeks .

30 голосов | спросил kapil.thakar 27 MarpmFri, 27 Mar 2015 16:47:14 +03002015-03-27T16:47:14+03:0004 2015, 16:47:14

7 ответов


40

Я вижу некоторые вещи, которые вы можете использовать для улучшения кода.

Использовать скорую помощь

Если переданный номер x меньше 9, подпрограмма может немедленно вернуть 0.

Устранить кратные 2

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

Устранить неиспользуемые переменные

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

Рассмотрим реализацию тестовой программы

Вы, по-видимому, уже провели какое-то тестирование, но публикация теста с кодом, который будет рассмотрен, может помочь другим людям правильно проверить код.

Объединяя все вместе

Вот что я придумал, используя все эти предложения:

#include <stdio.h>
#include <assert.h>

int isDivby9(int x)
{
    while (0 == (x & 1)) {
        x >>= 1;
    }
    if(x<9)
        return 0;

    int divby8 = x >> 3;
    while(divby8 >= 9) {
        divby8 -= 9;
    }
    return divby8 == (x & 7);
}

int main()
{
    for (int i=1; i < 1000000; ++i) 
        assert(isDivby9(i) == (i%9 == 0));
}

Результаты

На моей машине (64-разрядный Linux-ящик) исходный код запускается через 2,3 секунды, а версия выше завершается через 1,5 секунды; значительное улучшение производительности с идентичными математическими результатами. Для сравнения, простой подход в ответе @ Edenia занимает 18,8 секунды на той же машине.

Все были скомпилированы с gcc 4.9.2 с оптимизацией -O2.

Обновленный алгоритм

Я не мог перестать думать об этом вопросе, потому что знал, что есть лучший алгоритм, но просто не мог думать об этом. Я наконец натолкнулся на этот превосходный ответ на аналогичный вопрос в StackOverflow. С этим превосходным ответом я перевел реализацию конечного автомата на C и придумал следующее:

#include <limits.h>

struct state {
    int nextstate[2];
};
int isDivby9 (int num)
{
    static const int HIGH_BIT = INT_MAX - (INT_MAX >> 1);
    static const struct state states[9] = { 
        {{0, 1}}, {{2, 3}}, {{4, 5}}, 
        {{6, 7}}, {{8, 0}}, {{1, 2}}, 
        {{3, 4}}, {{5, 6}}, {{7, 8}}
    };
    if (num < 0) 
        num = -num;        
    int s = 0;
    for ( ; num ; num <<= 1) {
        s = states[s].nextstate[(num & HIGH_BIT) ? 1 : 0];
    }
    return s==0;
}

Каждый бит, начиная с MSB, приводит конечный автомат в следующее состояние. Состояние хранится в переменной s, а ветви для битов 0 и 1 - это две записи nextstate , Он работает хорошо (включая отрицательные числа и ноль) и очень быстро. Фактически, на моей машине эта процедура занимает 0,045 секунды.

Обновленные результаты

В более сжатых тестах времени на моей машине и настройке всех подпрограмм для правильной работы с отрицательными номерами, вот что я нашел на этой машине:

  861092 modulus operator
 1152840 JS1
 1581770 gnasher729
 2479987 Simon
 8961866 Edward DFA function

Таким образом, оператор % является самым быстрым, за ним следует подпрограмма @ JS1, за которой следует @ gnasher729, а затем @ Simon's, за которым следует процедура DFA (с большим отрывом!)

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

Я узнал некоторые вещи, которые могут быть полезны в следующий раз, когда я работаю над синтезом своей собственной логики или встроенного микропроцессора без многократной инструкции.

ответил Edward 27 MarpmFri, 27 Mar 2015 17:37:33 +03002015-03-27T17:37:33+03:0005 2015, 17:37:33
18

После прочтения ответов gnasher729 и Саймона я был вдохновлен найти самый быстрый способ сделать это.

Анализ исходной функции

Основная проблема с исходной функцией заключается в том, что она использует только разделение на 8 трюков один раз. После этого он попадает в этот цикл:

    while(divby8 >= 9)
    {
        divby8 = divby8 - 9;
    }

Учитывая большое количество, этот цикл может итерации для миллионов итераций.

Более быстрые решения

Gnasher729 и Simon продемонстрировали решения, которые использовали небольшой цикл для уменьшения исходного числа на 6 и 3 бит соответственно. Основываясь на их работе, я придумал следующее оптимизированное решение:

int div9(int x)
{
    x = (x >> 15) - (x & 0x7fff);
    x = (x >> 9) - (x & 0x1ff);
    x = (x >> 6) + (x & 0x3f);
    x = (x >> 3) - (x & 0x7);
    return x == 0;
}

Эта функция предназначена для использования для 32-битных положительных целых чисел. Для 64-битных положительных целых чисел вы можете добавить эту строку в начале:

    x = (x >> 30) + (x & 0x3fffffff);

Если отрицательные целые числа разрешены, вы можете добавить эту строку в начале:

    if (x < 0) x = -x;

Просто для удовольствия

Исходный вопрос не позволяет умножить или по модулю. Но просто для удовольствия, давайте посмотрим, какой будет самый быстрый метод. Например, насколько быстро используется modulo?

int div9(int x)
{
    return (x % 9) == 0;
}

Вот самое быстрое решение, которое я мог бы придумать, используя умножение. Это решение основано на ответе на stackoverflow . Сдвиг на 6 состоит в том, чтобы получить исходное число, достаточно маленькое, чтобы работать с многократным трюком.

int div9(int x)
{
    x = (x >> 6) + (x & 0x3f);
    return (x * 0xe38e38e4u) < 0x1c71c71c;
}

Функция синхронизации

Вот основная функция моей программы синхронизации. Он проверяет все значения от 0 до 0x7ffffff4. Я решил сделать это таким образом, чтобы избежать использования i%9 в тестовом цикле, поскольку i%9 может занимать значительное количество времени по сравнению с фактическими проверенными функциями .

int main(void)
{
    int i;
    for (i=0;i<0x7ffffff5;i+=9) {
        if (div9(i+0) == 0) break;
        if (div9(i+1) == 1) break;
        if (div9(i+2) == 1) break;
        if (div9(i+3) == 1) break;
        if (div9(i+4) == 1) break;
        if (div9(i+5) == 1) break;
        if (div9(i+6) == 1) break;
        if (div9(i+7) == 1) break;
        if (div9(i+8) == 1) break;
    }
    if (i != 0x7ffffff5) {
        printf("Failed on 0x%08x\n", i);
        return 1;
    }
    return 0;
}

Результаты синхронизации

 Author              Time (seconds)
------              --------------
JS1 (multiply)           2.23
JS1 (modulo)             3.35
JS1 (shifts)             5.70
Gnasher729              16.90
Simon (opt)             30.40
Simon                   53.40

Симон (опт) - это его функция, имеющая только сдвиг на 3 петли. Как вы можете видеть, это быстрее, не имея цикла, который проверяет полномочия 2.

ответил JS1 28 MarpmSat, 28 Mar 2015 13:58:24 +03002015-03-28T13:58:24+03:0001 2015, 13:58:24
16

Я не проверял, работает ли ваш код, я предполагаю, что это происходит, так как вы так говорите.

Ваш код не соответствует последовательности

if(divby8 == (orgx - (olddivby8 << 3)))
{
   //...
}

против

else{
   //...
}

и

if(x>=9) vs while(divby8 >= 9)

Я предлагаю использовать автоматизированный инструмент форматирования.

Избегать вложенности

Вы можете избежать вложенности, инвертируя внешний оператор if и возвращающий 0. Ваше гнездование не настолько глубокое, что это не серьезная проблема.

Необработанный код

Я не вижу смысла иметь эти строки.

else{
    status = 0;
}
x = divby8;

Комментарии

Вы должны добавить комментарии, объясняющие почему . Пример: В if(x>=9) вы можете добавить

// It cannot be divisible by 9 if it is less than 9 
ответил Bhathiya Perera 27 MarpmFri, 27 Mar 2015 17:18:55 +03002015-03-27T17:18:55+03:0005 2015, 17:18:55
10

Если вход большой, код будет работать очень и очень долго. Если вы изменили тип от int до int64_t, он может работать вечно.

Можно использовать тот факт, что 64% ​​9 == 1, поэтому (64x + y)% 9 == (x + y)% 9.

while (x >= 64) x = (x >> 6) + (x & 0x3f);
while (x >= 9) x -= 9;

Даже для самого большого x у вас будет меньше 20 итераций циклов.

ответил gnasher729 28 MaramSat, 28 Mar 2015 07:22:32 +03002015-03-28T07:22:32+03:0007 2015, 07:22:32
8
int divides9 (int number)
{
    int num;

    for(num = number; num > 0; num -= 9);

    return (num == 0);
}

С учетом ваших ограничений я мог бы придумать это, похоже, отличающееся от вашего текущего подхода. И поменьше.


Не только лишний, но и очень запутанный: Имена, которые вы используете, очень длинные. Случай с верблюдом не очень читается с длинными именами.

  • PreferCamelCaseOverSnakeCaseForLongNames

  • prefer_snake_case_over_camel_case_for_long_names

Какой из них проще читать? Правильно.

Итак, вы можете заменить isDivby9 на is_divisible_by9 или если вы хотите придерживаться сокращенных имен - isdivsbl и указать номер, который должен быть проверьте как аргумент функции.

Что такое orgx? В то время, когда я его читал, я не мог понять.

olddivby8 еще хуже. Это означает все имена. Придерживайтесь стиля и старайтесь придумать короткое имя, которое имеет прекрасный смысл и в значительной степени самоочевидно.


Используйте пробелы. Особенно между объявлением и выражением if.


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

ответил Edenia 27 MarpmFri, 27 Mar 2015 17:27:00 +03002015-03-27T17:27:00+03:0005 2015, 17:27:00
4

Вы отметили этот вопрос «новичок», но этот альготизм на geeksforgeeks довольно продвинут. Вы уверены, что должны использовать его для простого повторного сложения или вычитания? Фактически, вы все еще выполняете повторное вычитание на 9, когда вы это делаете:

while(divby8 >= 9)
    {
        divby8 = divby8 - 9;
    }

Таким образом, вы не получаете полного преимущества побитового алгоритма.

Я изменил код Эдварда (все хорошие предложения там), чтобы более точно реализовать алгоритм, который вы связали. Усиление производительности значимо - приурочено к моей машине на 0,018 с для этого против 3,497 для @ Edward's и 41,787s для @ Edenia's.

#include <stdio.h>
#include <assert.h>

int isDivby9(int x)
{
    // early bailout when x is 0, otherwise the factor of 2 loop does not terminate.
    if (x == 0) {
        return 1;
    }

    // eliminate factors of 2
    while (0 == (x & 1)) {
        x >>= 1;
    }

    // repeatedly reduce the problem to testing whether (floor(x/8) - x%8) is divisible by 9
    // until we can use the trivial case of whether a number smaller than 9 is divisible by 9.
    // Note that x & 7 is not equal to x % 8 for negative numbers,
    // nor is floor(x/8) appropriate for negative numbers.
    // The algorithm requires a truncation toward 0, not to the next lower integer like floor() or >> 3 does.
    while (x >= 9) {
        x = (x >> 3) - (x & 7);
    }

    return x == 0;
}

int main()
{
    for (int i=0; i < 1000000; ++i)
        assert(isDivby9(i) == (i%9 == 0));
}
ответил Simon 27 MarpmFri, 27 Mar 2015 23:30:24 +03002015-03-27T23:30:24+03:0011 2015, 23:30:24
4

Мне действительно не понравилось то, что @Edenia написал код, мой похож на нее, только я думаю, что это намного чище и просто.

    int isDivisibleBy(int number, int divisor)
    {
        for (int i = 0; i <= number; i += divisor)
        {
            if (i == number)
            {
                return 1;
            }
        }
        return 0;
    }

, и это будет работать для любого набора чисел и делителей.


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

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


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

int isDivisibleBy(int number, int divisor)
{
    int i = 0;
    while (i < number)
    {
        i += divisor;
    }
    return i == number;
}
ответил Malachi 27 MarpmFri, 27 Mar 2015 18:13:58 +03002015-03-27T18:13:58+03:0006 2015, 18:13:58

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132