blocks|key|342083|text|实际上，LSB方法实际上会让这件事变得更容易。在C中：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|342084|MSB方法：|342085|/*+
Returns+1+if+divisble+by+3,+otherwise+0
Note:+It+is+assumed+'input'+format+is+valid
*/
int+is_divisible_by_3_msb(char+*input)+{
++unsigned+value+=+0;
++char+*p+=+input;
++if+(*p+==+'1')+{
++++value+&=+1;
++}
++p%2B%2B;
++while+(*p)+{
++++if+(*p+!=+',')+{
++++++value+<<=+1;
++++++if+(*p+==+'1')+{
++++++++ret+&=+1;
++++++}
++++}
++++p%2B%2B;
++}
++return+(value+%25+3+==+0)+?+1+:+0;
}|code-block|syntax|javascript|342086|LSB方法：|342087|/*+
Returns+1+if+divisble+by+3,+otherwise+0
Note:+It+is+assumed+'input'+format+is+valid
*/
int+is_divisible_by_3_lsb(char+*input)+{
++unsigned+value+=+0;
++unsigned+mask+=+1;
++char+*p+=+input;
++while+(*p)+{
++++if+(*p+!=+',')+{
++++++if+(*p+==+'1')+{
++++++++value+&=+mask;
++++++}
++++++mask+<<=+1;
++++}
++++p%2B%2B;
++}
++return+(value+%25+3+==+0)+?+1+:+0;
}|342088|就我个人而言，我很难相信其中一个会与另一个有显着的不同。|342089|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|S|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|T|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|U|8|@]|9|@]|A|$G|H]]|$1|M|3|N|5|6|7|V|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

Actually the LSB method would actually make this easier. In C:

MSB method:



<pre class="lang-c prettyprint-override"><code>/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_msb(char *input) {
 unsigned value = 0;
 char *p = input;
 if (*p == '1') {
 value &amp;= 1;
 }
 p++;
 while (*p) {
 if (*p != ',') {
 value &lt;&lt;= 1;
 if (*p == '1') {
 ret &amp;= 1;
 }
 }
 p++;
 }
 return (value % 3 == 0) ? 1 : 0;
}
</code></pre>

LSB method:

<pre class="lang-c prettyprint-override"><code>/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_lsb(char *input) {
 unsigned value = 0;
 unsigned mask = 1;
 char *p = input;
 while (*p) {
 if (*p != ',') {
 if (*p == '1') {
 value &amp;= mask;
 }
 mask &lt;&lt;= 1;
 }
 p++;
 }
 return (value % 3 == 0) ? 1 : 0;
}
</code></pre>

Personally I have a hard time believing one of these will be significantly different to the other.

blocks|key|345494|text|你需要使用算术模3来做所有的计算。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|345495|MSB：|345496|number=0
while(!eof)
++++n=input()
++++number=(number+*2+%2B+n)+mod+3

if(number+==+0)
++++print+divisible|code-block|syntax|javascript|345497|LSB：|345498|number+=+0;
multiplier+=+1;
while(!eof)
++++n=input()
++++number+=+(number+%2B+multiplier+*+n)+mod+3
++++multiplier+=+(multiplier+*+2)+mod+3

if(number+==+0)
+++print+divisible|345499|这是大体的想法。|345500|现在，你要做的就是理解，为什么，，这是正确的。|offset|length|style|BOLD|345501|是的，你自己做作业;)|345502|entityMap^0|0|0|0|0|0|0|B|5|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Z|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|10|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|11|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|12|8|@]|9|@]|A|$G|H]]|$1|M|3|N|5|6|7|13|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|14|8|@$Q|15|R|16|S|T]]|9|@]|A|$]]|$1|U|3|V|5|6|7|17|8|@]|9|@]|A|$]]|$1|W|3|-4|5|6|7|18|8|@]|9|@]|A|$]]]|X|$]]

You need to do all calculations using arithmetic modulo 3. This is the way

MSB:

<pre><code>number=0
while(!eof)
 n=input()
 number=(number *2 + n) mod 3

if(number == 0)
 print divisible
</code></pre>

LSB:

<pre><code>number = 0;
multiplier = 1;
while(!eof)
 n=input()
 number = (number + multiplier * n) mod 3
 multiplier = (multiplier * 2) mod 3

if(number == 0)
 print divisible
</code></pre>

This is general idea...

Now, your part is to understand why this is correct.

And yes, do homework yourself ;)

blocks|key|342107|text|我认为Nathan+Fellman在a部分和b部分是正确的(除了b需要一个额外的状态:你需要跟踪你的数字位置是奇数还是偶数)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|342108|我认为C部分的诀窍是在每一步否定last的值。也就是说，0到0，1到2，2到1。|offset|length|style|CODE|342109|entityMap^0|0|G|4|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@$D|L|E|M|F|G]]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

I think Nathan Fellman is on the right track for part a and b (except b needs an extra piece of state: you need to keep track of if your digit position is odd or even).

I think the trick for part C is negating the <code>last</code> value at each step. I.e. 0 goes to 0, 1 goes to 2 and 2 goes to 1.

blocks|key|345611|text|嘿嘿|type|unstyled|depth|inlineStyleRanges|entityRanges|data|345612|LSB的状态表：|345613|S+I+S'+O
0+0+0++1
0+1+1++0
1+0+2++0
1+1+0++1
2+0+1++0
2+1+2++0|code-block|syntax|javascript|345614|说明:0可以被3整除。0+<<+1+%2B+0+=+0。如果是S+==+0，请重复使用S+=+(S+<<+1+%2B+I)+%25+3和O+=+1。|offset|length|style|CODE|345615|MSB的状态表：|345616|S+I+S'+O
0+0+0++1
0+1+2++0
1+0+1++0
1+1+0++1
2+0+2++0
2+1+1++0|345617|说明:0可以被3整除。0+>>+1+%2B+0+=+0。如果是S+==+0，请重复使用S+=+(S+>>+1+%2B+I)+%25+3和O+=+1。|345618|S'与上面不同，但O的工作原理相同，因为对于相同的情况(00和11)，S'是0。由于O在两种情况下是相同的，O_LSB+=+O_MSB，所以要使MSB与LSB一样短，或者反之亦然，只需使用两者中最短的一个即可。|345619|entityMap^0|0|0|0|B|E|T|6|15|K|1Q|5|0|0|0|B|E|T|6|15|K|1Q|5|0|0|2|Z|2|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Z|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|10|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|11|8|@$K|12|L|13|M|N]|$K|14|L|15|M|N]|$K|16|L|17|M|N]|$K|18|L|19|M|N]]|9|@]|A|$]]|$1|O|3|P|5|6|7|1A|8|@]|9|@]|A|$]]|$1|Q|3|R|5|F|7|1B|8|@]|9|@]|A|$G|H]]|$1|S|3|T|5|6|7|1C|8|@$K|1D|L|1E|M|N]|$K|1F|L|1G|M|N]|$K|1H|L|1I|M|N]|$K|1J|L|1K|M|N]]|9|@]|A|$]]|$1|U|3|V|5|6|7|1L|8|@$K|1M|L|1N|M|N]|$K|1O|L|1P|M|N]]|9|@]|A|$]]|$1|W|3|-4|5|6|7|1Q|8|@]|9|@]|A|$]]]|X|$]]

Heh

State table for LSB:

<pre><code>S I S' O
0 0 0 1
0 1 1 0
1 0 2 0
1 1 0 1
2 0 1 0
2 1 2 0
</code></pre>

Explanation: 0 is divisible by three. <code>0 &lt;&lt; 1 + 0 = 0</code>. Repeat using <code>S = (S &lt;&lt; 1 + I) % 3</code> and <code>O = 1</code> if <code>S == 0</code>.

State table for MSB:

<pre><code>S I S' O
0 0 0 1
0 1 2 0
1 0 1 0
1 1 0 1
2 0 2 0
2 1 1 0
</code></pre>

Explanation: 0 is divisible by three. <code>0 &gt;&gt; 1 + 0 = 0</code>. Repeat using <code>S = (S &gt;&gt; 1 + I) % 3</code> and <code>O = 1</code> if <code>S == 0</code>.

<code>S'</code> is different from above, but O works the same, since <code>S'</code> is 0 for the same cases (00 and 11). Since O is the same in both cases, O_LSB = O_MSB, so to make MSB as short as LSB, or vice-versa, just use the shortest of both.

blocks|key|340767|text|如果一个数的位数之和能被3整除，则该数可被3整除。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|340768|因此，您可以将数字相加，得到总和：|340769|如果和大于或等于10，则使用相同的方法，如果它是3，6，9，则它是可除的，如果和不同于3，6，9，则它不是可除的|340770|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

A number is divisible by 3 if the sum of it's digits is divisible by 3. 

So you can add the digits and get the sum:

<ul>
<li>if the sum is greater or equal to 10 use the same method</li>
<li>if it's 3, 6, 9 then it is divisible</li>
<li>if the sum is different than 3, 6, 9 then it's not divisible</li>
</ul>

blocks|key|342966|text|input++"0":+++++++(0)++output+1
inputs+"1,0,0":+++(4)++output+0
inputs+"1,1,0,0":+(6)++output+1|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|342967|最后一个输入不应该是12吗，或者我误解了这个问题？|unstyled|offset|length|style|CODE|342968|entityMap^0|0|A|2|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|N|8|@$G|O|H|P|I|J]]|9|@]|A|$]]|$1|K|3|-4|5|F|7|Q|8|@]|9|@]|A|$]]]|L|$]]

<pre><code>input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
</code></pre>

shouldn't this last input be <code>12</code>, or am i misunderstanding the question?

blocks|key|345673|text|这里..。一些新的东西。如何检查任意长度的二进制数(即使是数千位数)是否能被3整除。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|345674|​|345675|📷|atomic|offset|length|345676|345677|-->((0))<---1--->()<---0--->(1)++++++++ASCII+representation+of+graph|code-block|syntax|javascript|345678|从照片上看。|345679|当你得到一个1或0的时候，如果数字在这个圆圈内，你就会留在那个圆圈里。，，|345680|，|ordered-list-item|345681|345682|，当你得到一个1或一个零时，如果数字在这个圆圈内，你就会留在那个圆圈里。但是，如果数字在一条线上，那么您将穿过这条线。|345683|重复步骤2，直到所有数字都被占用为止。|345684|如果您最终到达双圆圈，则二进制数可以被3整除。|345685|345686|你也可以用它来生成被3整除的数字，我不认为它很难转换成一个电路。|345687|1个使用图表的示例...|345688|1100000000000101111111111111101可被3整除(再次以双圆结束)|345689|你自己试试吧。|345690|在将二进制数转换为以10为基数的数字时，您也可以使用类似的技巧执行MOD+10。(10个圆圈，每个圆圈双圈，表示模0到9的值)|345691|EDIT:这是用于从左到右的数字，修改有限状态机以接受相反的语言并不难。|style|BOLD|345692|注意:图的ASCII码表示中的+()表示单个圆，而(())表示双圆。在有限状态机中，这些状态称为状态，双圆是接受状态(表示最终可被3整除的状态)。|345693|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/ccb93f5ebbac41823e29a20448678600.png|imageAlt^0|0|0|0|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|5|0|0|F|0^^$0|@$1|2|3|4|5|6|7|1S|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1T|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|1U|8|@]|9|@$G|1V|H|1W|1|1X]]|A|$]]|$1|I|3|C|5|6|7|1Y|8|@]|9|@]|A|$]]|$1|J|3|K|5|L|7|1Z|8|@]|9|@]|A|$M|N]]|$1|O|3|P|5|6|7|20|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|21|8|@]|9|@]|A|$]]|$1|S|3|T|5|U|7|22|8|@]|9|@]|A|$]]|$1|V|3|T|5|6|7|23|8|@]|9|@]|A|$]]|$1|W|3|X|5|U|7|24|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|U|7|25|8|@]|9|@]|A|$]]|$1|10|3|11|5|U|7|26|8|@]|9|@]|A|$]]|$1|12|3|-4|5|6|7|27|8|@]|9|@]|A|$]]|$1|13|3|14|5|6|7|28|8|@]|9|@]|A|$]]|$1|15|3|16|5|6|7|29|8|@]|9|@]|A|$]]|$1|17|3|18|5|6|7|2A|8|@]|9|@]|A|$]]|$1|19|3|1A|5|6|7|2B|8|@]|9|@]|A|$]]|$1|1B|3|1C|5|6|7|2C|8|@]|9|@]|A|$]]|$1|1D|3|1E|5|6|7|2D|8|@$G|2E|H|2F|1F|1G]]|9|@]|A|$]]|$1|1H|3|1I|5|6|7|2G|8|@$G|2H|H|2I|1F|1G]]|9|@]|A|$]]|$1|1J|3|-4|5|6|7|2J|8|@]|9|@]|A|$]]]|1K|$1L|$5|1M|1N|1O|A|$1P|1Q|1R|-4]]]]

Here... something new... how to check if a binary number of any length (even thousands of digits) is divisible by 3.

<a href="http://i25.tinypic.com/23oe41.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/QeLBq.png" alt="divisible-by-3 state machine"></a>

<pre><code>--&gt;((0))&lt;---1---&gt;()&lt;---0---&gt;(1) ASCII representation of graph
</code></pre>

From the picture.

<ol>
<li>You start in the double circle.</li>
<li>When you get a one or a zero, if the digit is inside the circle, then you stay in that circle. However if the digit is on a line, then you travel across the line.</li>
<li>Repeat step two until all digits are comsumed.</li>
<li>If you finally end up in the double circle then the binary number is divisible by 3.</li>
</ol>

You can also use this for generating numbers divisible by 3. And I wouldn't image it would be hard to convert this into a circuit.

1 example using the graph...

11000000000001011111111111101 is divisible by 3 (ends up in the double circle again)

Try it for yourself.

You can also do similar tricks for performing MOD 10, for when converting binary numbers into base 10 numbers. (10 circles, each doubled circled and represent the values 0 to 9 resulting from the modulo)

EDIT: This is for digits running left to right, it's not hard to modify the finite state machine to accept the reverse language though.

NOTE: In the ASCII representation of the graph () denotes a single circle and (()) denotes a double circle. In finite state machines these are called states, and the double circle is the accept state (the state that means its eventually divisible by 3)

Write code to determine if a number is divisible by 3. The input to the function is a single bit, 0 or 1, and the output should be 1 if the number received so far is the binary representation of a number divisible by 3, otherwise zero.

Examples:

<pre><code>input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
</code></pre>

This is based on an interview question. I ask for a drawing of logic gates but since this is stackoverflow I'll accept any coding language. Bonus points for a hardware implementation (verilog etc).

Part a (easy): First input is the MSB.

Part b (a little harder): First input is the LSB.

Part c (difficult): Which one is faster and smaller, (a) or (b)? (Not theoretically in the Big-O sense, but practically faster/smaller.) Now take the slower/bigger one and make it as fast/small as the faster/smaller one.

Check if a number is divisible by 3

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋 

腾讯云代码助手

CODING DevOps

Cloud Studio

SDK中心

API中心

命令行工具

编写代码以确定一个数是否能被3整除。该函数的输入是一个单位，0或1，如果到目前为止收到的数是一个可被3整除的数的二进制表示，则输出应为1，否则为零。示例：input  "0":       (0)  output 1inputs "1,0,0":   (4)  output 0inputs "1,1,0,0": (6)...

问检查一个数字是否能被3整除
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问检查一个数字是否能被3整除EN