时光博客

c

DIV7的位运算实现

题目如下

一个数除以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求余,同样不利用乘法、除法、取模

编写PHP 5.6的C扩展

编写PHP的C扩展,有三种方式:

1、External Modules:外部模块,也就是编译成共享库,用dl()函数动态加载

好处:

(1)不需要重新编译PHP
(2)PHP体积小,因为不需要编译进PHP

缺点:

(1)每次*.php脚本执行都需要用dl()去加载,效率较低
(2)每次都要调用dl()

2、Built-in Modules:编译进PHP

好处:

(1)不需要动态加载,模块在php脚本里面可以直接使用
(2)不需要将模块编译成.so共享库,因为直接编译进PHP

缺点:

(1)对模块的改变都需要重新编译PHP
(2)因为编译进PHP,所以PHP二进制文件较大,而且多占点内存

3、The Zend Engine:Zend核心里实现(略……有兴趣的话可以看Zend API)

Note:推荐用第2种方式,直接编译进PHP,但是在下面示例里,我们编译成外部模块,因为,外部模块不需要重新编译PHP,所以在测试阶段先编译成共享库,测试完后再用第2种方式重新编译进PHP。

继续阅读

©2008-2017 - 时光博客 Ucloud

京ICP备15052479号返回顶部