《深入理解计算机系统》第二章习题2_66

最近打算把《深入理解计算机系统》再读一遍，说实话这本书读多少遍都不嫌多，每读一遍都会有收获。这次决心把书中的习题整个过一遍，并把其中我认为比较典型的、有意思的写城博文记录一下，恩，这就是这篇博文的由来。恳请各路大神拍砖。

一. 问题描述（鉴于我这不忍直视的翻译水平，我就直接贴书中的问题描述了）：

Generate mask indicating leftmost 1 in x. Assume w = 32.

For example 0xFF00 -> 0x8000, and 0x6600 --> 0x4000.

If x = 0, then return 0.

int leftmost_one(unsigned int x);

二. 结果正确但不符合题意的解决方法：

刚开始看到这个问题，想了想，突然间有了一个很简单的解决方案，所以赶紧写代码试了一下，恩，效果不错，所得结果是正确的。（窃喜），但再仔细看题目要求，这和说好的不一样啊！！帖代码：

int leftmost_one(unsigned int x)
{
	unsigned int base = 0x80000000;
	while(base)
	{
		if((x & base))
			break;
		base >>= 1;
	}
}

意思很简单，既然题目中假设w=32，那么我想，只需要从32位下最大的数base开始和x进行与运算，如果结果不为零，那么这个base就是x中最左边的那个1所表示的数了。

三. 分析：

题目的要求是，让我们生成一个掩码，用来标识出x中最左边的那个1。（换句话说是让我们找到一个掩码，使得x除了最左边为1的那一位，别的位都置为0），很遗憾我们上面的代码并没有产生任何叫掩码的东西。以下来分析一下这个问题：

书中题目下方有个小提示，“把x转换成形如 000...111..的形式”，好吧，竟然是这么含蓄的提示。

假设此时的字长w = 8，假设 x = 00010110，那么结果必然为 0001 0000，什么样的掩码能达到这个效果呢，我们想到了这个mask = xxx1 0000,(x 既可以为0，也可以为1）

那么 x & mask = 0001 0110 & xxx1 0000 = 0001 0000。现在问题的关键就是怎么才能由x生成这个掩码mask：（我们这时要想一想那个含蓄的提示了）

在x中最左边的1左边的位全为0或者没有，那么我们可以通过位运算把最左边的1右边的所有位都置为1（好拗口），如下：

0001 1111

然后在此基础上取反，有：1110 0000，然后再右移一位，有 0111 0000，哈哈，此时我们的掩码就生成了。帖代码：

int leftmost_one(unsigned int x)
{
	unsigned int mask = x;
	mask |= mask >> 1;
	mask |= mask >> 2;
	mask |= mask >> 4;
	mask |= mask >> 8;
	mask |= mask >> 16;
	mask = (~mask) >> 1;
	return x & mask;
}