-当x是二进制数时如何找到x mod 3？不允许使用转换为十进制然后使用 % 运算符。
-eg- 如果 x 为 1101，则输出应为 1，但不要将 1101 转换为 13，然后按 % 3 查找
问问题
4148 次
6 回答
4
既然您说“字符串”，我将添加以下技术：
请注意，如果您0在二进制数的末尾追加，则将其值加倍。如果在末尾追加1，则将其加倍并加 1。
也就是说，如果您已经处理了直到某个数字的所有数字（将此数字称为该数字a），并且您知道a % 3 = x对于 some x=1, 2 or 0，那么您可以告诉以下内容：
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.
于 2013-11-14T13:27:06.087 回答
1
如果您注意到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 个偶数次方 (2^0,2^2) 和 1 个 2 (2^3) 的奇数次幂
因此 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"));
}
}
于 2013-11-14T14:06:33.740 回答
1
它非常快速和创新。
二进制中的 3 是 11，即以 10 为底的 11。所以我们知道一个数可以被 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);
}
于 2013-11-14T13:26:08.130 回答
0
要判断一个十进制数是否能以 10 为基数被 9 整除，只需将其数字相加并重复直到只有一个数字。如果该数字是 0、3、6 或 9，则它可以被 9 整除。
这基于相同的原理，但对于在基数 4 中可被 3 整除的数字：
int mod3 (int x) {
if (x<0) x = -x;
while (x & 0x7fff0000) x = ((x & 0x7fff0000)>>16) + (x & 0x0000ffff);
while (x & 0xff00) x = ((x & 0xff00)>>8) + (x & 0x00ff);
while (x & 0xf0) x = ((x & 0xf0)>>4) + (x & 0x0f);
while (x & 0x0c) x = ((x & 0x0c)>>2) + (x & 0x03);
while (x>=3) x -= 3;
return x;
}
于 2013-11-14T13:51:08.670 回答
0
A % B 等价于 A - (floor(A/B) * B)。如果您可以使用二进制数执行减法、乘法和整数除法，那么您可以模拟%运算符而不实际使用它。
于 2013-11-14T13:21:56.610 回答
0
这里的概念是，如果您在任何二进制数的末尾添加 0 或 1，则数字将加倍加上 0 或 1，具体取决于是否设置了下一个位，并且提醒也将变为 [previous_reminder*2 + (0 或 1)]。并在这一步之后计算提醒：提醒=提醒％3;
这是java代码：
public static void main(String[] args) {
int[] arr = { 1, 1, 0, 1, 1, 0, 0, 1, 1, 1};
// Assumed first bit is always set therefore reminder will be 1.
int reminder = 1;
for (int i = 1; i < arr.length; i++) {
reminder = reminder * 2 + arr[i];
reminder = reminder % 3;
}
System.out.println(reminder);
}
于 2016-09-18T04:32:52.907 回答