%我需要在不使用,/或的情况下找出一个数字是否可以被 3 整除*。给出的提示是使用atoi()函数。知道怎么做吗？
问问题
26118 次
16 回答
70
当前的答案都集中在十进制数字上，当应用“添加所有数字并查看是否除以 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;
}
于 2010-08-06T07:03:18.137 回答
59
减去 3 直到你
a) 命中 0 - 数字可以被 3 整除
b) 得到一个小于 0 的数字 - 数字不可整除
-- 编辑版本以修复注意到的问题
while n > 0:
n -= 3
while n < 0:
n += 3
return n == 0
于 2010-08-06T07:02:17.840 回答
32
将数字拆分为数字。将数字相加。重复直到你只剩下一位数字。如果该数字是 3、6 或 9，则该数字可以被 3 整除。（并且不要忘记将 0 作为特殊情况处理）。
于 2010-08-06T06:57:22.487 回答
17
虽然转换为字符串然后将十进制数字相加的技术很优雅，但它要么需要除法，要么在转换为字符串的步骤中效率低下。有没有办法将这个想法直接应用于二进制数，而无需先转换为十进制数字字符串？
事实证明，有：
给定一个二进制数，其奇数位之和减去其偶数位之和可被 3 整除，当且仅当原始数可被 3 整除。
举个例子：取数字 3726，它可以被 3 整除。在二进制中，它是111010001110。所以我们取奇数，从右往左移动，分别是[1, 1, 0, 1, 1, 1]；这些的总和是5。偶数位为 [0, 1, 0, 0, 0, 1]；这些的总和是2。5 - 2 = 3，由此我们可以得出结论，原来的数可以被 3 整除。
于 2010-08-06T09:35:58.883 回答
6
一个能被 3 整除的数，iirc 有一个特点，就是它的数字之和能被 3 整除。例如，
12 -> 1 + 2 = 3
144 -> 1 + 4 + 4 = 9
于 2010-08-06T06:59:21.543 回答
6
面试问题本质上是要求你想出（或已经知道）以 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 - 有许多除数规则
于 2010-08-06T07:11:33.877 回答
5
我在 Java 中的解决方案仅适用于 32 位unsigned 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 的数字。最后一步通过将掩码向右移动适当的次数来检查可分性。
于 2010-10-09T19:20:22.640 回答
5
给定一个数字 x。将 x 转换为字符串。逐个字符解析字符串。将每个解析的字符转换为一个数字（使用 atoi()）并将所有这些数字相加成一个新的数字 y。重复该过程，直到您的最终结果数字为一位数。如果那个数字是 3,6 或 9，则原始数字 x 可以被 3 整除。
于 2010-08-06T07:00:56.570 回答
3
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 比较每个值！
等等，我们甚至可以通过组合它们之间的自然数来测试每个数字。
于 2010-12-13T16:31:38.110 回答
3
你没有标记这个 C，但既然你提到atoi了，我将给出一个 C 解决方案：
int isdiv3(int x)
{
div_t d = div(x, 3);
return !d.rem;
}
于 2010-08-11T08:01:06.990 回答
2
如果数字中的所有数字相加时的结果为 3、6 或 9，则该数字可以被 3 整除。例如，3693 可以被 3 整除，因为 3+6+9+3 = 21 和 2+1=3，而 3 是能被 3 整除。
于 2010-08-06T06:58:41.593 回答
2
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. 在这里阅读更多。
于 2013-09-15T05:49:46.553 回答
1
如果一个数字的所有数字之和都可以被 3 整除，那么一个数字可以被 3 整除。所以您可以将每个数字作为输入数字的子字符串，然后将它们相加。然后你会重复这个过程，直到只有一个数字的结果。
如果这是 3、6 或 9，则该数字可被 3 整除。
于 2010-08-06T07:00:22.683 回答
0
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();
}
}
}
于 2012-02-25T11:28:20.450 回答
0
- 这是我想出的一个伪algol。
让我们跟随 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
于 2015-05-18T21:24:32.167 回答
-1
这是每个人都应该知道的优化解决方案......
资料来源：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;
}
于 2012-02-24T16:48:49.693 回答