检测一个数能否被3整除
如果一个数的每个位相加之和能被3整除，则这个数就可以被3整除。例如612各位之和为9，则可以被3整除。但是这个解决方法并不高效，我们需要取得每一位，然后再一个个相加。
观察二进制，我们可以找到一个模式来判断一个数能否被3整除。如果所有的偶数位出现1的次数为 even_count, 奇数位出现1的次数为 odd_count，两者只差如果是3的倍数，那么这个数就是3倍数。
例如：23 (00…..0010111) even_count=3, odd_count = 1. 3-1 不能被2整除，所以不是3的倍数。
其实原因很简单，这是由于10^k≡1(mod3)。这样我们可将10、100、1000……等都看做1，最后将各个数位的数字加起来，若能被3整除，原来的数即可被3整除。
四、七、十三、十六……进制数与十进制数一样，都可以用这个方法。
三、六、九、十二、十六……进制数很明显，可以直接看出。
其他进制数略微麻烦一点，仅以二进制数为例分析如下：
根据：10^(2k+1)+1≡0(mod11)
10^2(k+i)+10^2k+1≡0(mod11)
我们得到二类定可被11(3)整除字符串：
①11、1001、100001、10000001……（3、9、33、129……）
②10101，1010001，101000001……（21、81、321……273）
任一二进制数n的1字符要么在右数奇数位，要么在偶数位。假如奇数位有j个1字符，偶数位有k个1字符。令每个奇数位上的1字符选择一个（且只能一个）偶数位上的1字符，当j=k时，将构成j个①类字符串；假如j≠k，剩余∣j-k∣个1字符必定同在奇数（或偶数）位。若n≡0(mod11),则∣j-k∣≡0(mod11)，也就是说这些剩余的1字符可以划分为∣j-k∣/3个②类字符串。
由此可见，利用以上两类字符串判断，不会有遗漏，也不会有重复。
例如，100011100101111001101000
000000000000000000000000
在一个二进制数中，这些字符串可能有很多划分方法，且往往是相互交叉、嵌套在一起的，因此运用起来不够方便。为此根据实践经验推演出几个从左至右划分的，更实用、更利于直观判断的字符串组合。
令：A=00……0（由奇数个连续的0组合的字符串）
这样我们的判断就得到一套新的字符串，其中：
0≡0（mod11）
1≡1（mod11）
1A≡10（mod11）1AB≡10（mod11）1 A1BA20≡10（mod11）
显然0≡0（mod11） 1A01≡0（mod11）无需再证明，如果仅仅是1A01字符串的交叉、嵌套，重要不将其中某个偶数个连续的0字符给段为两个奇数个0字符串，我们一定可依序将它们重新划分为若干个1A01字符串。
A是由奇数个连续的0组合的字符串，AA=A0(或0A)，不能够重复出现。
B中间不包含A字符串，BB=B，也不会重复出现。
若A与B重复交叉，其中部分字符必定构成了一个1ABA1字符串。
下面证明1A1BA21≡0（mod11）
由于B=1……1（中间为任意多个字符组合，但不包含A字符串），如果我们将其中包含的1A01字符串按顺序逐一消除（注意，至少要保留1个或2个字符），最终的结果必然剩余“1”或“11”。也就是说，1A1BA21简化为1A11A21或1A111A21两种形式。
1A11A21是前已经证明过的②字符串，毫无疑问，它≡0（mod11）；
而1A111A21是1A01与11的嵌套组合字符串，故，1A111A21≡0（mod11）。
于是，1A1BA21≡0（mod11）
最后，证明判断余数的字符串是否正确且无遗漏。
这些字符串一定是1A01、1A1BA21字符串去掉尾部某些字符后形成的。
1A01能够且只能导致三种结果：
1≡1（mod11） 1A≡10（mod11） 1A0≡1（mod11）
对于1A1BA21，显然我们可以只考虑从B字符串开始舍去尾部的部分字符。
舍去某个1字符后的所有字符，只有一种1AB
舍去某个0字符后的所有字符，只有两种1A1BA2、1A1BA20
根据前面的分析，我们同样可以认为，如果我们将B字符串中包含的1A01字符串按顺序逐一消除（注意，至少要保留1个或2个字符），这三种字符串最终简化为：1A1与1A11、1A11A2与1A111A2、1A11A20与1A111A20。
显然1A1=1A0+1
由于1A0≡1（mod11）
故
又1A11=1A+11
故1A11≡10（mod11）
从而证明了1AB≡10（mod11）
例如：101、1011、10110000111、1000100111100111……
如果n的二进制末位为0，那么n和n>>1同时被3整除或者不整除
如果n的二进制末位为1，那么n和(n>>1)-1同时被3整除或者不整除
bool IsTimesOf3(int n)
{
int s;
if (n < 0)
n = - n;
while (n > 0)
{
s = n & 1;
n >>= 1;
n = n - s;
}
return (n == 0);
}
if (n < 0)
n = - n;
while (n > 0)
{
s = n & 1;
n >>= 1;
n = n - s;
}
return (n == 0);
}
二进制末尾为0 为偶数 假设n=2k；又因为 n能被3整除 所以 n=2*3K=6k;那么 n右移1位 相当于除以2 那么 n=n/2；n=3k ；3K一定会整除3； （不能整除 同理可得 即 n=3k+1）； 如果n二进制末尾为1，那么是奇数 n=2k+1；又因为n可以被3整除，那么n=3*（2k+1）; n右移1位，再减去1.就等于 3k，3k必然能被3整除（不能整除 同理可得）
