检查数字是否可被9整除

#1 楼

我看到了一些您可能想使用的改进代码的方法。 x。

消除2的倍数

由于9和2没有公因子，因此可以通过将传入的0右移直到最低有效位为非零。

消除未使用的变量

通过对代码进行较小的重组，您可以消除大多数变量并使代码更短，更快。并且更容易阅读。

考虑实施测试程序

您显然已经进行了一些测试，但是发布带有要检查的代码的测试可能会帮助其他人检查代码正确地。

将它们放在一起

这是我使用所有这些建议得出的结果：

#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秒。

所有程序均使用带有-O2优化的gcc 4.9.2进行了编译。知道有一个更好的算法，但没想到。我终于在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开始的每一位都将状态机驱动到下一个状态。状态保存在变量x中，并且s和0位的分支是两个1条目。它运作良好（包括负数和零），并且速度非常快。实际上，在我的机器上，此例程需要0.045秒。

更新结果

在我的机器上进行更简洁的定时测试，并调整所有例程以使其在负数上也能正常工作，这是我在这台机器上发现的内容： >

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

所以nextstate运算符是最快的，其次是@ JS1的例程，接着是@ gnasher729的例程，接着是@Simon的，接着是DFA例程（相当大的距离！）

自然地，这在具有不同体系结构的不同机器上可能会有所不同，因此一如既往，建议您在自己的实际硬件上使用定时例程。

我学到了一些可能对下次我要合成自己的逻辑或在没有乘法指令的嵌入式微处理器上工作。

#2 楼

阅读gnasher729和Simon的答案后，我受到启发，找到了最快的方法来做到这一点。仅使用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;

只是为了好玩

原始问题不允许乘法或取模。但是，只是为了好玩，让我们看看什么是最快的方法。例如，简单地使用模运算有多快？

此解决方案基于此stackoverflow答案。将6移位是为了使原始数字小到足以使用乘法技巧。我的计时程序的功能。它测试从0到0x7ffffff4的所有值。我选择这样做是为了避免在测试循环中使用i%9，因为与被测试的实际功能相比，i%9可能要花费大量时间。

时间结果

 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
 

西蒙（opt）是他的函数，只有3个循环移位。如您所见，无需循环即可检查2的次方，因此速度更快。

#3 楼

我没有检查您的代码是否有效，因为您这样说，所以我认为它可以。

您的代码缺乏一致性

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

vs

else{
   //...
}

和

if(x>=9)与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 

#4 楼

如果输入很大，则代码将运行非常长的时间。如果将类型从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次循环迭代。

#5 楼

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语句之间。



使用位运算进行这种算术很少见，而且并不总是那么漂亮。特别是如果不需要它们。正是由于这种情况很少见，除非您是唯一的选择，否则不应该使用它们。它们很难调试。

#6 楼

您将此问题标记为“初学者”，但是geeksforgeeks上的算法非常先进。您确定要在简单的重复加法或减法上使用它吗？实际上，当您执行以下操作时，您仍在进行9的重复减法操作： br />
我更改了@Edward的代码（那里所有好的建议），以更忠实地实现您链接的算法。性能提升非常明显-在我的计算机上，此时间为0.018s，@ Edward为3.497s，@ Edenia为41.787s。

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

#7 楼

我真的不喜欢@Edenia编写代码的方式。我的就像她的一样，只是我认为它更简洁明了： />
我之所以更喜欢我的代码，是因为for循环在单个块中完成；尽管这可能是美观的，但对我来说似乎仍然更干净。
我们将数字相加，所以在最后一次运行时，我们将通过增加除数直到达到数字来查看是否落在数字上。
答案将适用于负数，因此请小心在其中插入负数。该代码也是如此；如下所示，并且只检查一次结果，并且对于它的操作仍然很简单。