题目如下

一个数除以7,不能用除法,乘法以及模运算,写出算法并实现

解题思路

既然不能用常规的函数,那么我们就像想别的办法,最容易想到的,当然还是位运算,关于位运算,leetcode上有一道题,属于经典的位运算题目,我博客之前也做过分析,猛击这里阅读「 Single Number II 

首先假设这个数为N,这个数可以表示为 N = 8 * A + B,为什么要用8,是因为8是最靠近7的,且可以通过二级制位移来产生的数字,例如:A >> 3 = A * 2 ^ 3 = A * 8

有了上面的结论后,那么就有了下面的递归

equation.png - 大小: 1.75 KB - 尺寸: 282 x 18 - 点击打开新窗口浏览全图

从上面的公式中很容易看出来递归,那么A、B究竟该怎么表示呢?回到公式 N = 8 * A + B,不难看出,

A = N / 8  且 B = N & 7

A = N / 8 很好理解,可以看做8是被除数,N是商

B = N & 7 这个又回到了,我们的位运算的与运算上,因为B < 8,所以要获得B 只需要获取 N 的二级制最小位开始的后三位即可,所以这里是 & 0111,直接返回后3位的值

上面的理解了,程序就很容易写出来了

代码如下

#include <stdio.h>
int div7(int n) {
    if(n < 8)
    {
        return (n + 1) >> 3; //此处+1是为了处理n为7的情况
    }
    else
    {
        return (n >> 3) + div7((n >> 3) + n & 7);
    }
}
int main(){
    int n = 14;
    int x;
    x = div7(n);
    printf("%d div 7 is : %d\n", n, x);
} 

编译之后运行 14 div 7 is : 2

这里留一道地考题,如何求 任意数正整数对7求余,同样不利用乘法、除法、取模