blocks|key|2515073|text|A%25B等同于A-+(floor(A/B)+*+B)。如果可以用二进制数执行减法、乘法和整数除，那么就可以模拟%25运算符，而不实际使用它。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2515074|entityMap^0|1I|1|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|K|8|@]|D|@]|E|$]]]|G|$]]

A % B is equivalent to A - (floor(A/B) * B). If you can perform subtraction, multiplication, and integer division with your binary numbers, than you can simulate the <code>%</code> operator without actually using it.

blocks|key|41800|text|它速度很快，而且很有创意。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|41801|所以我们知道一个数可以被11整除，如果奇数位的位数之和与偶数位的位数之和之差为0或可被11整除。|41802|因此，添加偶数放置的1s和奇数放置的1。有所不同。请检查下面的程序，我们正在做完全相同的事情。如果你有字符串，同样也适用。|offset|length|style|CODE|41803|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%2B%2B;
++++++++}
++++++++n=n>>1;
++++++++if(n==0)break;
++++++++if((n&1)==1){
++++++++++++even%2B%2B;
++++++++}
++++}
++++return+isDivisible(even-odd);
}|code-block|syntax|javascript|41804|有关更多信息，请访问this和this。|41805|entityMap|0|LINK|mutability|MUTABLE|url|http://www.cs.colorado.edu/~srirams/classes/doku.php/the_binary_world#binary_divisibility_by_3_check|1|http://www.geeksforgeeks.org/write-an-efficient-method-to-check-if-a-number-is-multiple-of-3/^0|0|0|A|2|I|1|0|0|A|4|0|F|4|1|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|11|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|12|8|@$F|13|G|14|H|I]|$F|15|G|16|H|I]]|9|@]|A|$]]|$1|J|3|K|5|L|7|17|8|@]|9|@]|A|$M|N]]|$1|O|3|P|5|6|7|18|8|@]|9|@$F|19|G|1A|1|1B]|$F|1C|G|1D|1|1E]]|A|$]]|$1|Q|3|-4|5|6|7|1F|8|@]|9|@]|A|$]]]|R|$S|$5|T|U|V|A|$W|X]]|Y|$5|T|U|V|A|$W|Z]]]]

it's very fast and innovative.

3 in binary is 11 i.e. 11 in base 10. So we know a number is divisible by 11, if the difference of the sum of digits at odd places and the sum of its digits at even places, is either 0 or divisible by 11. 

So add the even placed <code>1s</code> and add the odd placed <code>1</code>. Take difference. Please check the below program, we are doing exactly same thing. If you have string same also applies.

<pre><code>public static boolean isDivisible(int n){
 if(n&lt;0){
 n=-n;
 }
 if(n==0)return true;
 if(n==1)return false;
 int even=0, odd=0;
 while(n!=0){
 if((n&amp;1)==1){
 odd++;
 }
 n=n&gt;&gt;1;
 if(n==0)break;
 if((n&amp;1)==1){
 even++;
 }
 }
 return isDivisible(even-odd);
}
</code></pre>

For more you can follow <a href="http://www.cs.colorado.edu/~srirams/classes/doku.php/the_binary_world#binary_divisibility_by_3_check" rel="nofollow">this</a> and <a href="http://www.geeksforgeeks.org/write-an-efficient-method-to-check-if-a-number-is-multiple-of-3/" rel="nofollow">this</a>.

blocks|key|2725067|text|由于您说的是"string"，我将添加以下技术：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2725068|请注意，如果将0附加到二进制数的末尾，则会使其值加倍。如果在末尾附加1，则将其加倍并加1。|offset|length|style|CODE|2725069|也就是说，如果您已经处理了直到某个数字的所有数字(将该数字称为直到该数字的a)，并且您知道某个x=1,+2+or+0的a+%25+3+=+x，那么您可以得出以下结论：|2725070|a0+%25+3+=+(2+*+a)+%25+3+=+((2+%25+3)+*+(a+%25+3))+%25+3+=+(2+*+(a+%25+3))+%25+3
a1+%25+3+=+(2+*+a+%2B+1)+%25+3+=+((2+%25+3)+*+(a+%25+3)+%2B+(1+%25+3))+%25+3+=+(2+*+(a+%25+3)+%2B+1)+%25+3|code-block|syntax|javascript|2725071|通过这种方式，您可以轻松地进行以下区分：|2725072|Current+mod+%7C+Next+digit+%7C+New+mod
------------%2B------------%2B---------
+++0++++++++++++0++++++++++++0
+++0++++++++++++1++++++++++++1
+++1++++++++++++0++++++++++++2
+++1++++++++++++1++++++++++++0
+++2++++++++++++0++++++++++++1
+++2++++++++++++1++++++++++++2|2725073|也就是说，您可以从左向右遍历字符串(假设使用msbf表示法)，并根据表更新new+mod。您可以从current+mod+=+0开始。|2725074|entityMap^0|0|7|1|Y|1|0|11|1|1B|B|1N|9|0|0|0|0|11|7|1D|F|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@$D|Y|E|Z|F|G]|$D|10|E|11|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|12|8|@$D|13|E|14|F|G]|$D|15|E|16|F|G]|$D|17|E|18|F|G]]|9|@]|A|$]]|$1|J|3|K|5|L|7|19|8|@]|9|@]|A|$M|N]]|$1|O|3|P|5|6|7|1A|8|@]|9|@]|A|$]]|$1|Q|3|R|5|L|7|1B|8|@]|9|@]|A|$M|N]]|$1|S|3|T|5|6|7|1C|8|@$D|1D|E|1E|F|G]|$D|1F|E|1G|F|G]]|9|@]|A|$]]|$1|U|3|-4|5|6|7|1H|8|@]|9|@]|A|$]]]|V|$]]

Since you said "string", I'll add the following technique:

Note that if you append <code>0</code> at the end of a binary number, you double it's value. If you append <code>1</code> at the end, you double it and add 1.

That is, if you have processed all digits up to a certain digit (call this number up to that digit <code>a</code>), and you know that <code>a % 3 = x</code> for some <code>x=1, 2 or 0</code>, then you can tell the following:

<pre><code>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
</code></pre>

This way, you can easily make the following distinction:

<pre><code>Current mod | Next digit | New mod
------------+------------+---------
 0 0 0
 0 1 1
 1 0 2
 1 1 0
 2 0 1
 2 1 2
</code></pre>

That is, you can traverse your string from left to right (assuming msbf notation) and update the <code>new mod</code> according to the table. You start with <code>current mod = 0</code>.

blocks|key|41814|text|要判断一个十进制数是否能被10为基数的9整除，只需将它的数字相加，然后重复，直到只有一个数字为止。如果数字是0、3、6或9，那么它可以被9整除。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|41815|这基于相同的原理，但适用于基数为4的可被3整除的数字：|41816|int+mod3+(int+x)+{
++if+(x<0)+x+=+-x;
++while+(x+&+0x7fff0000)+x+=+((x+&+0x7fff0000)>>16)+%2B+(x+&+0x0000ffff);
++while+(x+&+0xff00)+x+=+((x+&+0xff00)>>8)+%2B+(x+&+0x00ff);
++while+(x+&+0xf0)+x+=+((x+&+0xf0)>>4)+%2B+(x+&+0x0f);
++while+(x+&+0x0c)+x+=+((x+&+0x0c)>>2)+%2B+(x+&+0x03);
++while+(x>=3)+x+-=+3;
++return+x;
}|code-block|syntax|javascript|41817|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

To tell if a decimal number is divisible by 9 in base 10, just add its digits together and repeat until you have just one digit. If that digit is 0, 3, 6, or 9, then it's divisible by 9.

This works based on the same principle, but for numbers divisible by 3 in base 4:

<pre><code>int mod3 (int x) {
 if (x&lt;0) x = -x;
 while (x &amp; 0x7fff0000) x = ((x &amp; 0x7fff0000)&gt;&gt;16) + (x &amp; 0x0000ffff);
 while (x &amp; 0xff00) x = ((x &amp; 0xff00)&gt;&gt;8) + (x &amp; 0x00ff);
 while (x &amp; 0xf0) x = ((x &amp; 0xf0)&gt;&gt;4) + (x &amp; 0x0f);
 while (x &amp; 0x0c) x = ((x &amp; 0x0c)&gt;&gt;2) + (x &amp; 0x03);
 while (x&gt;=3) x -= 3;
 return x;
}
</code></pre>

blocks|key|2515192|text|如果你注意到2%5EN+mod+3++=+2+if+N+is+odd+&+2%5EN+mod+3+=+1+if+N+is+even+(它可以通过归纳法证明)，而且二进制no是2的幂和，所以只需检查1是以奇数还是偶数次方出现在字符串中，并对这些值进行连续求和。在模算术中有一个定理|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2515193|(a%2Bb%2Bc)%25m+=+((a)%25m+%2B+(b)%25m+%2B+(c)%25m+)%25m|code-block|syntax|javascript|2515194|例如：|2515195|X=+1101有2+(2%5E0,2%5E2)的2个偶数次幂和2+(2%5E3)的1个奇数次幂|2515196|因此res+=+(2*1+%2B2+)mod+3=4+mod+3=1|2515197|Java实现：-|2515198|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%2B%2B)+{

+++++++++++if(s.charAt(end)=='1')+{
+++++++++++++++if(i%252==0)
+++++++++++++++++++sum+=+sum+%2B+1;
+++++++++++++++else+sum+=+sum+%2B+2;
+++++++++++}+

+++++++++++end--;+
++++++++}
+++++++return(sum%253);+
++++}


++++public+static+void+main(String[]+args)+{

++++++++System.out.println(modulo3("1110"));
++++}

}|2515199|entityMap^0|6|1J|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@$9|X|A|Y|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|Z|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|10|8|@]|D|@]|E|$]]|$1|M|3|N|5|6|7|11|8|@]|D|@]|E|$]]|$1|O|3|P|5|6|7|12|8|@]|D|@]|E|$]]|$1|Q|3|R|5|6|7|13|8|@]|D|@]|E|$]]|$1|S|3|T|5|H|7|14|8|@]|D|@]|E|$I|J]]|$1|U|3|-4|5|6|7|15|8|@]|D|@]|E|$]]]|V|$]]

If You notice <code>2^N mod 3 = 2 if N is odd &amp; 2^N mod 3 = 1 if N is even</code> (it can be proved by induction) moreover binary no is sum of powers of 2 so just check if 1 appear in string at odd or even power and do a running sum of the values. There is theorem in modular arithmatic as 

<pre><code>(a+b+c)%m = ((a)%m + (b)%m + (c)%m )%m
</code></pre>

eg. 

x = 1101 there are 2 even powers of 2 (2^0,2^2) and 1 odd power of 2 (2^3) 

hence res = (2*1 + 2 )mod 3 = 4 mod 3 = 1 

Java implementation: - 

<pre><code>public class Modulus {

 public static int modulo3(String s) {

 int end = s.length()-1;
 int sum = 0;
 for(int i =0;i&lt;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"));
 }

}
</code></pre>

blocks|key|42929|text|这里的概念是，如果你在任何二进制数的末尾添加0或1，那么根据下一位是否设置，数字将加倍加0或1，提醒也将变为previous_reminder*2+%2B+(0或1)。并在此步骤后计算提醒:提醒=提醒%253；|type|unstyled|depth|inlineStyleRanges|entityRanges|data|42930|下面是java代码：|42931|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%2B%2B)+{
++++++++reminder+=+reminder+*+2+%2B+arr[i];
++++++++reminder+=+reminder+%25+3;
++++}
++++System.out.println(reminder);
}|code-block|syntax|javascript|42932|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

The concept here is if you add 0 or 1 at end of any binary number then number will be doubled plus 0 or 1 based on next bit set or not and reminder will also become [previous_reminder*2 + (0 or 1)]. 
And to calculate reminder after this step: reminder = reminder%3;

Here is java Code:

<pre><code>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 &lt; arr.length; i++) {
 reminder = reminder * 2 + arr[i];
 reminder = reminder % 3;
 }
 System.out.println(reminder);
}
</code></pre>

-How to find x mod 3 when x is binary number? Not allowed to use conversion to decimal and then using % operator.

-eg- if x is 1101 then output should be 1 but do not convert 1101 to 13 and then find by % 3

Binary string remainder 3

当x是二进制数时，-How找到x mod 3吗？不允许先转换为小数，然后再使用%运算符。--如果x为1101，则输出应为1，但是不会将1101转换为13，然后通过%3查找

问二进制字符串余数3
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问二进制字符串余数3EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问二进制字符串余数3
EN