[算法] check divisibility
看到一个算法题：不使用除法运算符(/)和模运算(%)判断一个数是否被形如2^n-1的数整除。
代码如下：
int checkdiv(int n,int k)
{
// 返回 n%(2^k-1)的结果
// n>=0,k>=2
if(n == 0)
return 0;
int m = (1<<k)-1; // m=2^k-1
while(n > m)
{
n = (n>>k) + (n&m);
}
if(m == n)
return 0;
else // m>n
return n;
}
原理如下：
n可以表示为
n=(n>>k)*(1<<k)+(n&m)
因此只需证明((n>>k)*(2^k)) ≡ (n>>k) (mod (2^k-1))，显然这是成立的。