当前位置： 文江博客 话题详情

检查一个数是否能被3整除

发布于 2024-09-12 18:37:27 字数 106 浏览 4 评论 0 原文

我需要在不使用 %、/ 或 * 的情况下确定一个数字是否能被 3 整除。给出的提示是使用atoi()函数。知道怎么做吗？

原文

I need to find whether a number is divisible by 3 without using %, / or *. The hint given was to use atoi() function. Any idea how to do it?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（16）

墟烟 2024-09-19 18:37:27

当应用“将所有数字相加，看看是否能除以 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;
}

The current answers all focus on decimal digits, when applying the "add all digits and see if that divides by 3". That trick actually works in hex as well; e.g. 0x12 can be divided by 3 because 0x1 + 0x2 = 0x3. And "converting" to hex is a lot easier than converting to decimal.

Pseudo-code:

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

[edit]
Inspired by R, a faster version (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;
}
回复 原文
未央 2024-09-19 18:37:27

减去 3，直到

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

b) 得到一个小于 0 的数字 - 数字不可整除

- 编辑版本以修复注意到的问题

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

Subtract 3 until you either

a) hit 0 - number was divisible by 3

b) get a number less than 0 - number wasn't divisible

-- edited version to fix noted problems

while n > 0:
    n -= 3
while n < 0:
    n += 3
return n == 0
回复 原文
猫腻 2024-09-19 18:37:27

将数字拆分为数字。将数字相加。重复直到只剩下一位数字。如果该数字是 3、6 或 9，则该数字可以被 3 整除。（并且不要忘记将 0 作为特殊情况处理）。

Split the number into digits. Add the digits together. Repeat until you have only one digit left. If that digit is 3, 6, or 9, the number is divisible by 3. (And don't forget to handle 0 as a special case).

回复 原文
萌︼了一个春 2024-09-19 18:37:27

虽然转换为字符串然后将十进制数字相加的技术很优雅，但它要么需要除法，要么在转换为字符串的步骤中效率低下。有没有一种方法可以将这个想法直接应用于二进制数，而不需要先转换为十进制数字字符串？

事实证明，有：

给定一个二进制数，它的奇数位之和减去偶数位之和可以被 3 整除，当且仅当原始数字可以被 3 整除。

举个例子：数字 3726，可以被 3 整除。在二进制中，这是 111010001110。所以我们取奇数位，从右开始向左移动，分别是[1, 1, 0, 1, 1, 1]；这些的总和是5。偶数位为[0, 1, 0, 0, 0, 1]；这些的总和是2。 5 - 2 = 3，由此可知原数能被3整除。

While the technique of converting to a string and then adding the decimal digits together is elegant, it either requires division or is inefficient in the conversion-to-a-string step. Is there a way to apply the idea directly to a binary number, without first converting to a string of decimal digits?

It turns out, there is:

Given a binary number, the sum of its odd bits minus the sum of its even bits is divisible by 3 iff the original number was divisible by 3.

As an example: take the number 3726, which is divisible by 3. In binary, this is 111010001110. So we take the odd digits, starting from the right and moving left, which are [1, 1, 0, 1, 1, 1]; the sum of these is 5. The even bits are [0, 1, 0, 0, 0, 1]; the sum of these is 2. 5 - 2 = 3, from which we can conclude that the original number is divisible by 3.

回复 原文
无所的.畏惧 2024-09-19 18:37:27

能被3整除的数，iirc有一个特点，就是它的各位数字之和能被3整除。例如，

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

A number divisible by 3, iirc has a characteristic that the sum of its digit is divisible by 3. For example,

12 -> 1 + 2 = 3
144 -> 1 + 4 + 4 = 9
回复 原文
一梦等七年七年为一梦 2024-09-19 18:37:27

面试问题本质上是要求你想出（或已经知道）以 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.

另请参阅

The interview question essentially asks you to come up with (or have already known) the divisibility rule shorthand with 3 as the divisor.

One of the divisibility rule for 3 is as follows:

Take any number and add together each digit in the number. Then take that sum and determine if it is divisible by 3 (repeating the same procedure as necessary). If the final number is divisible by 3, then the original number is divisible by 3.

Example:

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.

See also

回复 原文
落在眉间の轻吻 2024-09-19 18:37:27

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

Given a number x.
Convert x to a string. Parse the string character by character. Convert each parsed character to a number (using atoi()) and add up all these numbers into a new number y.
Repeat the process until your final resultant number is one digit long. If that one digit is either 3,6 or 9, the origional number x is divisible by 3.

回复 原文
长安忆 2024-09-19 18:37:27

我的 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 的数字。最后一步通过将掩码向右移动适当的次数来检查整除性。

My solution in Java only works for 32-bit unsigned 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;
}

It first reduces the number down to a number less than 32. The last step checks for divisibility by shifting the mask the appropriate number of times to the right.

回复 原文
无可置疑 2024-09-19 18:37:27

你没有标记这个C，但既然你提到了atoi，我将给出一个C解决方案：

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

You didn't tag this C, but since you mentioned atoi, I'm going to give a C solution:

int isdiv3(int x)
{
    div_t d = div(x, 3);
    return !d.rem;
}
回复 原文
热血少△年 2024-09-19 18:37:27 
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 比较
每个价值观！

等等，我们甚至可以通过组合自然数来测试每个数字。

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
*/
}

Following the same rule, to obtain the result of divisibility test by 'n', we can :
multiply the number by 0x1 0000 0000 - (1/n)*0xFFFFFFFF
compare to (1/n) * 0xFFFFFFFF

The counterpart is that for some values, the test won't be able to return a correct result for all the 32bit numbers you want to test, for example, with divisibility by 7 :

we got 0x100000000- (1/n)*0xFFFFFFFF = 0xDB6DB6DC
and 7 * 0xDB6DB6DC = 0x6 0000 0004,
We will only test one quarter of the values, but we can certainly avoid that with substractions.

Other examples :

11 * 0xE8BA2E8C = A0000 0004, one quarter of the values

17 * 0xF0F0F0F1 = 10 0000 0000 1
comparing to 0xF0F0F0F
Every values !

Etc., we can even test every numbers by combining natural numbers between them.

回复 原文
不念旧人 2024-09-19 18:37:27

如果一个数字中的所有数字相加得到的结果是 3、6 或 9，则该数字可以被 3 整除。例如，3693 可以被 3 整除，即 3+6+9+3 = 21 且 2+1=3 并且 3 为能被 3 整除。

A number is divisible by 3 if all the digits in the number when added gives a result 3, 6 or 9. For example 3693 is divisible by 3 as 3+6+9+3 = 21 and 2+1=3 and 3 is divisible by 3.

回复 原文
小鸟爱天空丶 2024-09-19 18:37:27 
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。点击此处了解更多信息。

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

On some compilers this is even faster then regular way: x % 3. Read more here.

回复 原文
青春如此纠结 2024-09-19 18:37:27

如果一个数字的所有数字之和都能被 3 整除，那么这个数字就可以被 3 整除。因此，您可以将每个数字作为输入数字的子字符串，然后将它们相加。然后，您将重复此过程，直到只有一位数字的结果。

如果是 3、6 或 9，则该数字可以被 3 整除。

well a number is divisible by 3 if all the sum of digits of the number are divisible by 3. so you could get each digit as a substring of the input number and then add them up. you then would repeat this process until there is only a single digit result.

if this is 3, 6 or 9 the number is divisable by 3.

回复 原文
独享拥抱 2024-09-19 18:37:27
  • 这是我想出的一个伪大陵五。

让我们跟踪 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 不会改变，因此，我提出的算法：

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
  • Here is a pseudo-algol i came up with .

Let us follow binary progress of multiples of 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

just have a remark that, for a binary multiple of 3 x=abcdef in following couples abc=(000,011),(001,100),(010,101) cde doest change , hence, my proposed algorithm:

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
回复 原文
梦情居士 2024-09-19 18:37:27

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();

        }
    }
}

C# Solution for checking if a number is divisible by 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();

        }
    }
}
回复 原文
时光瘦了 2024-09-19 18:37:27

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

来源：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;
}

Here is your optimized solution that every one should know.................

Source: 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;
}
回复 原文
~没有更多了~

关于作者

梦纸

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

烙印

文章 0 评论 0

singlesman

文章 0 评论 0

给自己一个微笑

文章 0 评论 0

独孤求败

文章 0 评论 0

晨钟暮鼓

文章 0 评论 0

我是自愿种绣球花的

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文