两道面试题

发表于   |   分类于

上午在社区看到有人分享自己的面试经历，正好有两道很有意思的题目，这里自己试试。

第一个是关于C中多进程的，fork的问题；第二个是位操作的，32位int按位反转的问题。

fork的问题

这个问题其实比较简单，就是考察对fork的理解。在apue的笔记中已经比较了解了。使用fork创建的新进程会得到父进程的代码、数据、堆、栈、缓存区和打开的文件列表的拷贝（实际上使用了写时复制COW技术，并不是一开始就执行父进程的完全副本），知道这个之后就能分析这个问题了，问题如下：

有下面的代码：

#include <stdio.h>
#include <unistd.h>

int main(void) {
    int i;
    for (i=0; i<2; i++) {
        fork();
        printf("-");
    }
    return 0;
}

假设fork()总是成功的，问打印出几个“-”？

根据上面的分析，在主线程运行到fork()的时候，产生了子进程，子进程有和父进程相同的i值，并在获得运行时接着从fork()往后运行，按照这样分析，主进程会fork出两个子进程，第一个子进程会fork出一个子进程，总共4个进程，主进程和第一个子进程打印两个”-“，后面两个进程分别可以打印一个”-“。这样分析可以打印出6个”-“。但显然这个问题没有这么简单。

无缓冲的输出

注意代码中使用的打印函数是带缓冲printf，我们知道write这些无缓冲的函数在调用时直接输出到目标，但是标准库中的printf是带缓冲的，如果标准输出连接到终端设备，则它是行缓冲的（按换行符冲洗），其他情况（如输出到文件）则是全缓冲的。

代码中使用的printf输出到标准输出，没有对输出重定向就是终端设备，也就是这里prinf是行缓冲的，打印的字符中又没有使用换行符，所以打印的字符会被缓冲！这样fork时，子进程会得到父进程标准输出的缓冲区。这样分析的话，最后两个进程分别会得到父进程的一个缓冲去的横杠，然后打印出来。

这样应该会有8个”-“的输出了。但问题也许更加复杂。

父子进程执行顺序

自己动手编译运行这段代码，会发现结果和我们分析的并不一样，并没有输出8个横杠，并且如果多次运行的话，结果可能还会不一样，可能大部分时候只打印了4个，有时2个，有时候6个，反而很少（基本不会）打印8个横杠。

可以猜想，这是因为父子进程执行顺序不确定导致的。fork之后，父进程先执行还是子进程先执行是不确定的。这取决于内核的调度算法，如果要确定父子进程的执行顺序，需要某种形式的通信，一般使用信号机制来同步，我们这里简单一点，使用让父进程睡眠，子进程先执行的方式，看看效果就可以理解了。

由于父子进程执行顺序不确定，所以可能主进程退出了，子进程还没调度执行，所以就只打印了两个横杠，可能子进程执行了一段，后两个子进程却没有执行，就可能打印4个横杠，就是这样导致了输出不确定（主进程退出后，后面进程的输出就不会输出到终端了）。下面我们修改一下代码，让所有进程都可以执行：

#include <stdio.h>
#include <unistd.h>

int main(void) {
    int i;
    pid_t pid;
    for (i=0; i<2; i++) {
        if ((pid=fork()) <0) {
            printf("fork error");
        } else if (pid == 0) {
            printf("-%d/", getpid());
        } else {
            sleep(1);
            printf("-%d/", getpid());
        };
    }
    return 0;
}

这里顺便打印出进程id，用于分析。 我们使用sleep让父进程睡眠一秒，虽然这并不能完全保证子进程一定就被调度了，只是一般来说，可以认为这样保证了子进程执行了。。。

编译运行这一段后会看到结果是一段一段的打印出来的，这是在进程退出时会执行输出缓冲区的冲洗，让缓冲区的内容在终端回显。执行结果为：

-25633/-25634/-25632/-25635/-25633/-25633/-25632/-25632/

可以看到，这样结果和分析的是一样的，是8个输出，有两个进进程id输出了三次（主进程和第一个子进程），另外两个进程id均输出一次，其实4个进程分别输出了两次，只是后两个进程从父进程“继承”了缓冲区的内容。

这个题目大概就是这样的，网上有的分析其实不太对。没有考虑进程同步的问题。

整数按位反转

将一个32Bit 的二进制数 头尾反转过来，尽可能高效。要高效率的话最好就是位操作了。位操作一直不太会，只好先在网上看了一些思路。

一种直观的方式

一种直接的思路是，做给定数的一个拷贝，原数每次向右移位一次并与0x01取并（取到最后一位），拷贝向左移位一次，然后拷贝与原数取并后的结果位与。实现如下：

int main(void) {
    unsigned int v, r;
    int s;
    while(1) {
        printf("input int:");
        scanf("%u", &v);
        printIntAsBinary(v);
        r = v;	// r用来保存转换后的结果
        s = sizeof(v) * CHAR_BIT - 1;	// 如果最高位是0，则最后需要移位s
        for (v >>= 1; v; v >>= 1) {
            r <<= 1;
            r |= (v&1);
            s--;
        }
        r <<= s;	// v的最高位是0则最终结果需要左移
        printf("reversed:%u ", r);
        printIntAsBinary(r);
    }
}

其中的 printIntAsBinary是我实现的一个将int数按位输出的函数，其实现如下：

void printIntAsBinary(unsigned int n) {
    unsigned int mask = 0x80000000;
    for (mask>>=1; mask; mask >>= 1) {
        if (n & mask)
            printf("1");
        else printf("0");
    }
    printf("\n");
}

这个实现时间开销为unsigned int的位数。

批量按位操作

另外有一种一次多次位转换的方法，有点分治的意思，对于一个N-bit的数，开销为 5*lg(N)。

这个方法的思路就是先互换相邻两位，再以两位为单位互换相邻的4位，以此类推：

unsigned int v;	// 32位unsinged
// 5： 0101 ，第一步实现相邻两位互换
v = ((v >> 1) & 0x55555555) | (( v & 0x55555555) << 1);
// 3：0011，两位两位互换
v = ((v >> 2) & 0x33333333) | (( v & 0x33333333) << 2);
// 0x0f: 0000ffff，四位四位互换
v = ((v >> 4) & 0x0f0f0f0f) | (( v & 0x0f0f0f0f) << 4);
// 0x00ff: 00000000fffffff，八位八位互换
v = ((v >> 8) & 0x00ff00ff) | (( v & 0x00ff00ff) << 8);
// 最后左右互换，得到结果
v = ((v >> 16) | (v << 16);

这种方法对于N很大的情况速度很快，对于32位整数则和上面的方法差不多，不过对于位数更多的数需要再写位运算，上面的只是32位整数的。

参考：