我需要找到一个数字是否可以被3除尽而不使用%，/或*。给出的提示是使用atoi()函数。知道怎么做吗？
减去3直到你
a）命中0 - 数字可被3整除
b）得到一个小于0的数字 - 数字不可分割
- 编辑版本以修复已发现的问题
while n > 0:
n -= 3
while n < 0:
n += 3
return n == 0
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相比每个值！
等等，我们甚至可以通过组合它们之间的自然数来测试每个数字。
如果加上数字中的所有数字给出结果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整除。
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 =（000,011），（001,100），（010,101）cde doest改变，因此，我提出的算法：
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;
}
当应用“添加所有数字并查看是否除以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;
}
将数字拆分为数字。将数字加在一起。重复，直到只剩下一位数字。如果该数字为3,6或9，则该数字可被3整除。（并且不要忘记将0作为特殊情况处理）。
虽然转换为字符串然后将十进制数字加在一起的技术很优雅，但它要么需要除法，要么在转换为字符串步骤中效率低下。有没有办法直接将这个想法应用于二进制数，而不首先转换为十进制数字串？
事实证明，有：
给定二进制数，如果原始数字可被3整除，则其奇数位的总和减去其偶数位的总和可被3整除。
举一个例子：取数字3726，可以被3整除。在二进制中，这是111010001110。所以我们取奇数，从右边开始向左移动，它们是[1,1,0,1,1,1];这些的总和是5.偶数位是[0,1,0,0,0,1];这些的总和是2.5-2 = 3，从中我们可以得出结论，原始数字可以被3整除。
一个可被3整除的数字，iirc具有一个特征，即其数字的总和可被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.
给出一个数字x。将x转换为字符串。逐字符解析字符串。将每个已解析的字符转换为数字（使用atoi（））并将所有这些数字加到新的数字y中。重复此过程，直到最终结果数字为一位数。如果该一个数字是3,6或9，则原始数字x可被3整除。
我的Java解决方案仅适用于32位无符号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;
}
它首先将数字减少到小于32的数字。最后一步通过将掩码向右移动适当的次数来检查可分性。
你没有标记这个C，但既然你提到了atoi，我将给出一个C解决方案：
int isdiv3(int x)
{
div_t d = div(x, 3);
return !d.rem;
}