检查一个数字是否可以被3整除

减去3,直到

a)命中0-数字可被3整除

b)得到一个小于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 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];这些数字之和是 五 . 偶数位是[0,1,0,0,0,1];它们的和是 二 . 5-2=3,由此我们可以得出原始数可以被3整除的结论。

一个可以被3整除的数,其特征是它的数字和可以被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.

也见

• Wikipedia/Divisibility rule -对许多除数有许多规则

给定一个数字x。 将x转换为字符串。逐字符分析字符串。将每个解析的字符转换成一个数字(使用atoi())并将所有这些数字相加为一个新的数字y。 重复这个过程,直到最终的结果数是一位数字长。如果这个数字是3、6或9,那么原始数字x可以被3整除。

我在Java中的解决方案只适用于32位 未签名的 int S.

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*0xf0f0f1=10万0000 1 与0xf0f0f0f比较 每一个价值!

等等,我们甚至可以通过在每个数字之间组合自然数来测试它们。

如果一个数加起来的所有数字都给出结果3、6或9,则该数可以被3整除。例如,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 . 多读 here .

如果一个数的所有位数之和都可以被3整除,那么这个数就可以被3整除。所以你可以得到每个数字作为输入数字的子串,然后把它们加起来。然后重复这个过程,直到只有一个数字的结果。

如果这是3、6或9,这个数字可以被3整除。

一个数可以被3除,如果它的位数之和可以被3除。您可以递归地使用这个定义,直到只剩下一个数字为止。如果结果是3、6或9,则原始数字可以被3整除,否则就不能。

例如:33333=>15(3+3+3+3+3)=>6(1+5),因此33333可以被3整除。

见 Divisibility rules

C用于检查数字是否可被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();

        }
    }
}

• 这是我想出的一个伪算法。

让我们按照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 =(000011),(001100),(010101) 化学需氧量 所以,我的提议不会改变 算法 :

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

这是您的优化解决方案,每个人都应该知道…………

来源: http://www.geeksforgeeks.org/archives/511

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