不许用%和/来实现求任意数除以3的余数

转载请注明出处，声明如下：

作者：peizhongyou

原文地址：

前几天参加一个编程竞赛，涉及到部分位运算的知识，准备不足挂了。事后在网上搜了一下位运算的介绍看到《位运算之美》这篇博客，其中提到了一个题目“不许用%和/来实现求任意数除以3的余数”感觉挺有意思，可惜博文中没有介绍方法，没办法只能自己解决了，解决方法如下：

第一种方法：循环减法

如果不用位运算，我们可以用一种最笨拙的方法，每次减3，直到小于3为止，剩多少自然是余数了（-_-）。

第二种方法：位运算递归求解

这种方法我们首先要分析一下，在什么情况下数字才能被3整除？整数表示时，我们都知道数字相加为3的倍数时可以被3整除，那么二进制表示时呢？

这里需要用到二项式定理中的一些知识了，我们知道

其中前m-1项都是可以被3整除的，余数项既是(-1)^m项，所以我们可以用一个余数项r来记录余数项的值，所以对于给定的整数a，我们只需要统计a二进制表示中1的位置即可，当1位于偶数位时那么余项为r-1（注意二进制表示从2^0开始），1在奇数位的时候余数项r+1，然后判定r的绝对值是否在3的范围内，如果还是大于3则迭代调用该过程，具体算法如下：

（1）判定整数a的符号，若a为负，则将a转化为正处理，并记录a的正负号；

（2）每次将a向右移动一位，判断a&1的值是否为1，并判定该位置的奇偶性（r&1），若为奇数则r+1，否则r-1；

（3）根据a的正负号做调整，若a为负值，则r = -r，判定|r|<3，若满足，当r>=0时返回r，若r<0时，返回r+3；

（4）若r>3，则重复1-3步，直到程序结束。

程序代码如下：

int divisorByThree(int a)

{

      bool mark(false);//用于标示出a是正数还是负数，是负数则为true

      int i(0);

      int even(0);

      int remainder(0);

      if (a < 0)

      {

         mark = true;

         a = -a;

      }

      do 

      {

         if ((a&1)==1)//说明末尾位是1

         {

            even++;

            if ((even&1)==1)//说明1出现在奇数位上，这剩余值为正

            {

               remainder += 1;

            }

            else

           {

              remainder -=1;

           }

        }

       else

      {

          even++;

      }

       a >>=1;

      } while (a);

      if (mark)

      {

          remainder = -remainder;

      }

      if (abs(remainder)<3)//剩余值小于3，说明有可能被整除，或者剩余1或2

     {

          return (remainder>=0)?remainder:(remainder+3);

      }

      else

      {

          divisorByThree(remainder);

      }

}