检查一个数字是否可以被3整除
我需要find一个数字是否可以被3整除而不使用% ， /或* 。 给出的提示是使用atoi()函数。 任何想法如何做到这一点？
直到你减去3
a）命中0–数字被3整除
b）得到一个小于0的数字 – 数字是不可分的
– 编辑版本来解决注意到的问题
while n > 0: n -= 3 while n < 0: n += 3 return n == 0
当应用“添加所有数字并查看是否除以3”时，当前的答案都集中在十进制数字上。 这个技巧实际上在hex工作， 例如0x12可以被3除，因为0x1 + 0x2 = 0x3。 而“转换”为hex比转换为十进制要容易得多。
伪代码：
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日志日志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作为一个特殊情况）。
虽然将string转换为string然后将十进制数字加在一起的技巧是优雅的，但是在转换为string的步骤中，要么需要除法，要么效率低下。 有没有办法将这个想法直接应用到一个二进制数字，而不是先转换成一个十进制数字的string？
原来，有：
给定一个二进制数，如果原始数可以被3整除，那么奇数位减去其偶数位数之和就可以被3整除。
举个例子：取3726号，可以被3整除。在二进制中，这是111010001110 。 所以我们从右向左移动奇数，分别是[1,1,0,1,1,1]。 这些总和是5 。 偶数位是[0，1，0，0，0，1]; 这些总和是2 。 5 – 2 = 3，从中我们可以得出结论，原始数字可以被3整除。
面试问题实质上是要求你以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转换为一个string。 按字符分解string。 将每个parsing的字符转换为一个数字（使用atoi（）），并将所有这些数字合并成一个新的数字y。 重复这个过程，直到最后的结果数字是一位数字。 如果这个数字是3,6或9，则原始数字x可以被3整除。
一个可以被3整除的数字，iirc有一个特点，它的数字的总和可以被3整除。例如，
12 -> 1 + 2 = 3 144 -> 1 + 4 + 4 = 9
你没有标记这个C，但是既然你提到了atoi ，我会给出一个C的解决scheme：
int isdiv3(int x) { div_t d = div(x, 3); return !d.rem; }
我在Java中的解决scheme只适用于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; }
它首先将数字减less到小于32的数字。最后一步通过将掩码向右移动适当的次数来检查可分性。
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'得到整除testing的结果，我们可以：把数字乘以0x1 0000 0000 – （1 / n）* 0xFFFFFFFF与（1 / n）* 0xFFFFFFFF
与之相对应的是，对于某些值，testing将无法为您要testing的所有32位数字返回正确的结果，例如，可用7除法：
我们得到了0x100000000-（1 / n）* 0xFFFFFFFF = 0xDB6DB6DC和7 * 0xDB6DB6DC = 0x6 0000 0004，我们只testing四分之一的值，但是我们当然可以避免这种情况。
其他例子：
11 * 0xE8BA2E8C = A0000 0004，四分之一的值
17 * 0xF0F0F0F1 = 10 0000 0000 1与0xF0F0F0F比较每个值！
等等，我们甚至可以通过在它们之间结合自然数来testing每个数字。
如果所添加的数字中的所有数字都给出结果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 。 在这里阅读更多。
如果数字的所有数字之和都可以被3整除，那么一个数字可以被3整除。所以你可以把每个数字作为input数字的一个子串，然后把它们相加。 那么你会重复这个过程，直到只有一个数字的结果。
如果是3,6或9，那么这个数字可以被3除。
用于检查数字是否可以被3除的C＃解决scheme
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(); } } }
这是你们每个人都知道的最佳解决scheme……………..
资料来源： 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; }
def divisible(a,b): d = a % b if d > 0: print "Not divisible" elif d == 0: print "Divisible" else: pass
整除（93.3）
一个数字可以被3整除，如果它的数字总和可以被3整除。你可以recursion地使用这个定义，直到你留下一个数字。 如果结果是3,6或9，原始数字可以被3整除，否则不可以。
例如：33333 => 15（3 + 3 + 3 + 3 + 3）=> 6（1 + 5）因此33333可以被3整除。
请参阅可分性规则
- 这是我想出的一个伪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
（001,010），（010,101） cde的变化是一个二元倍数3 ×abcdef ，因此，我提出的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
