n%3(n为2进制数)画出状态转移图.不要求画图,说明下怎么分析这个问题就行了

Question

n%3(n为2进制数)画出状态转移图.
不要求画图,说明下怎么分析这个问题就行了

Answer 1

//------------------------------------------------------
分为余数是0、1、2这三种状态.
状态跳转规则如下：
(这个规则是根据除法的步骤来定的,很容易理解.只要逐个比特地做除法,余数不停地左移,加下一个比特,试商,.)
0状态下（新进来的比特=0）,则跳到0状态；
0状态下（新进来的比特=1）,则跳到1状态；
1状态下（新进来的比特=0）,则跳到2状态；
1状态下（新进来的比特=1）,则跳到0状态；
2状态下（新进来的比特=0）,则跳到1状态；
2状态下（新进来的比特=1）,则跳到2状态；
//------------------------------------------------------
举例分析
（二进制的10101）%3,为方便表述,记为（二进制的d1d2d3d4d5）%3,
其中d1=1,d2=0,d3=1,d4=0,d5=1.
初始化状态为0状态.
d1=1进来,余数变成1（即跳转到1状态）；
d2=0进来,余数变成2（即跳转到2状态）；
d3=1进来,余数变成2,因为2左移一位然后加1变成5,5模3等于2.（即跳转到2状态）；
d4=0进来,余数变成1,因为2左移一位然后加0变成4,4模3等于1.（即跳转到1状态）；
d5=1进来,余数变成0,因为1左移一位然后加1变成3,3模3等于0.（即跳转到0状态）.