二进制数是否为三的倍数的检验方法和装置及检验芯片

具体实施方式

首先，对本发明的算法推导过程进行说明：

二进制数的特点是其每一位上的数字所代表的权重的数与3的倍数只差1或2，并且这种差值是有规律的，这种规律是若其权为奇数，则与3的倍数差1，若其权为偶数，则与三的倍数差2。

举例说明：

(1111_1111)₂＝2⁷+2⁶+2⁵+2⁴+2³+2²+2¹+2⁰

2⁷＝128＝129-1，129可以被3整除

2⁶＝64＝66-，66可以被3整除

2⁵＝32＝33-，33可以被3整除

……

2⁰＝1＝3-2，3可以被3整除

由此可见，可以将一个二进制数字拆成若干个3的倍数之和，再从低位中减去填充的1和2。

本发明的核心思想是：将一个二进制数拆成高位组与低位组两部分，其中，低位组的位数为减法器位宽，高位组的位数即该二进制数的总位数减去减法器位宽位数。进一步分析，每个奇数位所代表的数与偶数位所代表的数之和为三的倍数。因此，在作减法之前可以先计算有多少个奇数位的数，用该数减去偶数位的个数数。设被判断数的高位组(高位即总位数减去减法器位宽位数后高位的位数)中奇数位有p个1，偶数位有q个1，w＝p-q。w若为正，则该数能否被3整除的判断，等价于：判断低位组所表示的数减去w之差能否被3整除；w若为负，则该数能否被3整除的判断，等价于：判断低位组所表示的数减去w个2能否被3整除。

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

参照图1，图1是根据本发明二进制数是否为三的倍数检验方法实施例的步骤流程图，包括如下步骤：

步骤101：判断所述二进制数是否大于指定位数N(N>1)，若是，将所述二进制数拆分成低位组和高位组两部分；例如，将N设置为4，将二进制数拆分成Y位低位组和N-Y位高位组两部分。举例来说，对于二进制数，1110_0111_101│0_1000可以拆分为5位低位组部分和11位高位组部分。

步骤102：预置一查找表，所述查找表包括从0至2N中所有能够被3整除的数；在本例中，查找表应包括0到16之间所有能够被3整除的数，包括：0、3、6、9、12、15。

步骤103：确定所述高位组部分中的奇数位与偶数位，分别计算所述奇数位、所述偶数位的各位数字之和；按照上面的例子，给该16位二进制数的各位编序号：从最左侧低位开始：依次为第0位、第1位、第2位、...第15位，其中，高位组包括第5位至第16位，其奇数位各位数字之和为1+1+1+0+1+1＝5、所述偶数位的各位数字之和0+1+1+0+1＝3。

步骤104：判断所述奇数位的各位数字之和减去偶数位的各位数字之和的差值是否大于0，若是，则将所述低位组表示的数减去所述差值，获取执行结果；若否，将所述低位组表示的数作为被减数，减去将所述差值的绝对值左移一位后，获取二进制执行结果；根据上面的例子，奇数位的各位数字之和-偶数位的各位数字之和＝5-3＝2>0，属于前者，又所述低位组所表示的数01000为8：即所述的执行结果为8-2＝6。

步骤105：在所述查找表中查找所述二进制执行结果，如查找到，确定所述二进制数为三的倍数。否则，不是三的倍数。在本例中，能够在查找表中查到该执行结果，因此该二进制数1110_0111_1010_1000为3的倍数。

优选地，在所述拆分步骤中，通过如下方式确定所述低位组的位数，参照图2，包括如下步骤：

步骤201：令二进制数的总位数为N，令低位组的位数Y，则高位组中的位数为N-Y，令Y的初始值为4；

步骤202：判断不等式

$\frac{3(N-Y)+1}{2}\le 2^Y$

是否成立，若成立，则执行步骤204；若不成立，执行步骤203；

步骤203：令Y的值自加1，X＝N-Y；并且，返回执行步骤202；

步骤204：确定Y的值。

该低位组的位数确定方法主要是基于如下原理：

设被判断数为N位，低位组的位数为Y位，X为需要拆成3的倍数的和的权的位数，则设X＝N-Y，数的拆分如图3所示。

当X为偶数时，则高位中每两位所代表的权重的数之和恰要补充一个3。极端情况为高位中X位都有数，此时需要的被减数至少为$3\times \frac{X}{2}$

当X为奇数时，则高位中每两位所代表的权重的数之和恰要补充一个3，剩下的一个需要补充2或1。极端情况为高位中X位都有数，当需要补充的数是2时，此时需要的被减数至少为：

$3\times \frac{X-1}{2}+2=3\times \frac{X+\frac{1}{3}}{2}$

当需要补充的数是1时，此时需要的被减数至少为。

$3\times \frac{X-1}{2}+1=3\times \frac{X-\frac{1}{3}}{2}$

综合上述两种情况，需要补充的数在极端情况下为：

$3\times \frac{X-1}{2}+2=3\times \frac{X+\frac{1}{3}}{2}=\frac{3X+1}{2}$

而Y位二进制数能提供的最大的数为2^Y。

由上述分析可知，若N≥4，则需要满足：

$\frac{3X+1}{2}\le 2^Y$

优选地，所述查找表中的数值定为：0、3、6、9、12、15。因为如果一个二进制数若是3的倍数，按照上述方法得到的所述执行结果都应该都应该是三的倍数，为避免查找表中的数值过多，比较的次数过多，所以，该方法的一个优选实施方式可以选定：0、3、6、9、12、15。应该说明的是：本方法在此并不做任何限定，查找表中也可以采用更多的数值，比如：0、3、6、9、12、15、18、21，或者更多的能被3整除的数。

下面结合一个具体实例来详细说明本发明是如何实现一个多为二进制数是否为三的倍数的检验过程：

若判断二进制数1101_0110_1110是否为三的倍数，具体判断过程如下：首先预置一查找表，所述查找表包括0、3、6、9、12、15；然后通过如下步骤进行判断：

步骤401：判断被判断二进制数1101_0110_1110是否大于4位？如果否，则执行步骤402；如果是，执行步骤403。

因为该二进制数为16位，所以直接执行步骤403：

步骤403：计算高位组部分中奇数位各位数字之和与高位组部分中偶数位各位数字之和的差。

根据该被判断的数，首先将所述二进制数拆分成Y位低位组和N-Y位高位组两部分。其中，从Y＝4开始，验证不等式

$\frac{3X+1}{2}\le 2^Y$

是否成立。对于这个数，将X＝8，Y＝4代入不等式，不等式成立，因此，Y＝4，X＝8，不需要继续尝试新的Y值。并且，高位组部分中的奇数位各位数字之和为2，偶数位各位数字之和为3，奇数位的各位数字之和减去偶数位的各位数字之和的差值为W＝2-3＝-1。

步骤404：判断上述差值W是否大于0？若是，执行步骤405，若否，执行步骤406。

因为步骤403中得到的差值W＝-1，所以小于0，执行步骤406

步骤406：计算低位组表示的二进制数与W的绝对值左移一位的结果之差D。

因为低位组表示的数(1110)₂为14，将所述低位组表示的数减去所述差值的绝对值左移一位后得到的结果，获取的执行结果14-1×2＝12＝(1100)₂。

步骤407：将D作为新的被判断数，返回执行步骤401，判断被判断二进制数(1100)₂是否大于4位？

因为(1100)₂为4位，执行步骤402，判断该数是否为0，3，6，9，12，15之中的一个，因为(1100)₂表示12，所述查找表中能够查到，该二进制数(1101_0110_1110)₂为3的倍数。

这里需要说明的是：若将所述低位组表示的数减去所述差值的绝对值左移一位后得到的结果，获取的执行结果大于4位，也就是说在查找表中的最大值15小于该执行结果，则需要进行迭代，具体方法是，将执行结果作为新的被判断数进行判断，直到减法器在4位以内。对于一个26位的二进制数，低位组应划定为5位，在具体的判断过程中，则需要进行两次迭代判断。

参照图5，图5是根据本发明检验装置的实施例的结构示意图，包括如下结构：

拆分单元508，用于将所述二进制数被拆分成低位组和高位组两部分；

第一累加器501，用于计算所述二进制数的高位组部分奇数位各位数字之和；

第二累加器502，用于计算所述二进制数的高位组部分偶数位各位数字之和；

第一减法器503，该减法器的正输入端与所述第一累加器的输出端相连接，该减法器的负输入端与所述第二加法器的输出端相连接，用于计算述奇数位的各位数字之和减去偶数位的各位数字之和的差值；

第一选择器504，该选择器的第一输入端的输入信号为所述差值的符号位，该选择器的第二输入端的输入信号为所述差值，该选择器的第三输入端的输入信号为：所述差值通过一个反相器，一个左移位器后的值；

第二减法器505，该减法器的正输入端的信号为所述二进制数的低位组，该减法器的负输入端与所述选择器的输出端相连接；

查找表单元506，该查找表单元与所述第二减法器的输出端相连接，用于检查所述二进制数是否为三的倍数；

第二选择器507，该选择器的第一输入端与所述查找表的输出端相连接。

参照图6，图6是根据本发明检验装置的实施例的结构示意图，该装置可以用于检验低位组部分为4的二进制数。

根据本发明的另一方面，本发明还提供了一种芯片，该芯片包括所诉的检验装置。该检验装置的结构与上面的描述相同，在此不再赘述。

综上，在本发明中：

通过将二进制数拆分成低位组和高位组两部分，计算高位组中奇数位各位数字之和与偶数位各位数字之和的差、并根据差的正、负情况采取相应的手段获取执行结果，最后依据执行结果与查找表判断该数是否为3的倍数的技术手段，克服了现有技术中，数值转换复杂、所需减法器位宽较长所导致的芯片面积相对较大，工作效率低等缺陷，从而，能够用最少的资源，最快的运算效率，判断一个数，特别是一个较大的数是否是3的倍数。

本说明书中的各个实施例均采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似的部分互相参见即可。对于系统实施例而言，由于其与方法实施例基本相似，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。

以上对本发明所提供的一种二进制数是否为三的倍数检验方法、检验装置、芯片进行了介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。