二进制字符串余数3
当x是二进制数时，-How找到x mod 3吗？不允许先转换为小数，然后再使用%运算符。
--如果x为1101，则输出应为1，但是不会将1101转换为13，然后通过%3查找
回答 6
Stack Overflow用户
发布于 2013-11-14 21:27:06
由于您说的是"string"，我将添加以下技术：
请注意，如果将0附加到二进制数的末尾，则会使其值加倍。如果在末尾附加1，则将其加倍并加1。
也就是说，如果您已经处理了直到某个数字的所有数字(将该数字称为直到该数字的a)，并且您知道某个x=1, 2 or 0的a % 3 = x，那么您可以得出以下结论：
a0 % 3 = (2 * a) % 3 = ((2 % 3) * (a % 3)) % 3 = (2 * (a % 3)) % 3
a1 % 3 = (2 * a + 1) % 3 = ((2 % 3) * (a % 3) + (1 % 3)) % 3 = (2 * (a % 3) + 1) % 3通过这种方式，您可以轻松地进行以下区分：
Current mod | Next digit | New mod
------------+------------+---------
0 0 0
0 1 1
1 0 2
1 1 0
2 0 1
2 1 2也就是说，您可以从左向右遍历字符串(假设使用msbf表示法)，并根据表更新new mod。您可以从current mod = 0开始。
Stack Overflow用户
发布于 2013-11-14 21:26:08
它速度很快，而且很有创意。
所以我们知道一个数可以被11整除，如果奇数位的位数之和与偶数位的位数之和之差为0或可被11整除。
因此，添加偶数放置的1s和奇数放置的1。有所不同。请检查下面的程序，我们正在做完全相同的事情。如果你有字符串，同样也适用。
public static boolean isDivisible(int n){
if(n<0){
n=-n;
}
if(n==0)return true;
if(n==1)return false;
int even=0, odd=0;
while(n!=0){
if((n&1)==1){
odd++;
}
n=n>>1;
if(n==0)break;
if((n&1)==1){
even++;
}
}
return isDivisible(even-odd);
}Stack Overflow用户
发布于 2013-11-14 22:06:34
如果你注意到2^N mod 3 = 2 if N is odd & 2^N mod 3 = 1 if N is even (它可以通过归纳法证明)，而且二进制no是2的幂和，所以只需检查1是以奇数还是偶数次方出现在字符串中，并对这些值进行连续求和。在模算术中有一个定理
(a+b+c)%m = ((a)%m + (b)%m + (c)%m )%m例如：
X= 1101有2 (2^0,2^2)的2个偶数次幂和2 (2^3)的1个奇数次幂
因此res = (2*1 +2 )mod 3=4 mod 3=1
Java实现：-
public class Modulus {
public static int modulo3(String s) {
int end = s.length()-1;
int sum = 0;
for(int i =0;i<s.length();i++) {
if(s.charAt(end)=='1') {
if(i%2==0)
sum = sum + 1;
else sum = sum + 2;
}
end--;
}
return(sum%3);
}
public static void main(String[] args) {
System.out.println(modulo3("1110"));
}
}https://stackoverflow.com/questions/19978572
复制相似问题