C语言**位运算**终极剖析

C语言有时候被称为中级语言 ，即介于低级与高级之家的编程语言，原因是C语言不仅具有高级语言抽象机制，也具有低级语言直接操作变量个别位的能力，即我们即将要讨论的C语言强大的位 操作运算。C语言的这种能力也许会让你感到奇怪，但这种能力有时确实是必须的，或者至少是有用的，例如我们通常向硬件设备发送一两个字节来控制该设备，其 中的每一位都有特定的含义。许多压缩和加密操作都对单独的位进行操作。高级语言一般不处理这一级别的细节，可C语言在提供高级语言便利的同时也能够在典型的为汇编语言所保留的级别上工作 ，这就是C语言之所以能成为编写设备驱动程序和嵌入式代码首选语言的原因。

在正式进入美妙的主题C语言位运算 的讨论之前，我们必须先了解一些酷炫的背景知识：

一、二进制

说到计算机当然不能不知道二进制，就像玩吉他不能不知道五线谱一样，所谓二进制就是逢二进一 ，我们日常用的是十进制，逢十进一。另外，十进制的数字每一位对应一个10的某次幂，二进制的数字每一位对应一个2的某次幂。比如：

    (5017)₁₀ = 5 *10³ + 0 *10² + 1 *10¹ + 7 *10⁰ = 5000 + 0 + 10 + 7 = (5017)₁₀ 

    (1101)₂    = 1 *2³ +1 *2² + 0 *2¹ + 1 *2⁰ = 8 + 4 + 0 + 1 = (13)₁₀

二进制系统可以用1、0序列表示任何整数，这种系统非常始于数字计算机使用，数字计算机使用打开和关闭状态的组合来表示信息，二这些状态可以使用1和0来表示。

 

我们的计算机内部是怎么用二进制系统表示数字17的呢？通过简单的计算我们知道(57)₁₀ = 32 + 16 + 8 + 1 = (0111 1001)₂ ，即计算机中使用0111 1001这样一串数字表示十进制的57，因此在存储器上就有类似于如下的结构：

     |0 |1 |1 |1 |1 |0 |0 |1 |

顺便说一句，向上面那样8位(bit)存储位置称为一个字节(byte)，另外需要注意 的是：上面的01111001之所以表示一个十进制数字57(当然也就是二进制数字01111001)，而不是表示一个马桶，完全取决于 系统对此序列的解释方式，对每一位的解释方式的不同，就可以导致此序列表示意思的不同。计算机世界里没有母牛也没有马桶，有且仅有 枯燥的1、0序列！记住了。

 

二、符号

表示有符号数的最简单的方法是用一位来表示符号的正负，比如最高位比如1000 0011表示-3，0000 0011表示+3，但是这种表示方法的缺点是会有两个怪异的负零-0和正零+0。

解决这个问题的方法是采用二进制补码机制：

正数的时候最高位是0，不求补码，因此0000 0011（以一个字节为例）表示+3；负数的时候最高位是1，表示的数值是减一取反 （符号位不动），即把1000 0011先减1变成1000 0010再取反变成1111 1101，即1111 1101表示-3。反过来 ，当你知道存储器中有序列1111 1101且它表示的是一个负整数时，解释的方法就是取反加一（符号位不动），1111 1101取反得1000 0010再加一得1000 0011，即它表示的是-3。

 

在这种系统中+0就是0000 0000，而此时的1000 0000则表示-128(这个特殊，不遵循补码机制，硬性规定)。

 

okay，废话不多说，C语言的位操作罗列如下，重点会讲移位运算 ：

（位逻辑运算府）

一、位取反：~

    非常简单，~符号用于把每一位翻转，比如~(1001 0010) = (0110 1101)。

二、位与：&

    学过数电就知道，与操作就是只有两个位都为1时才为1，否则为0，比如：(1001 0011) & (0011 1101) = (0001 0001)

三、位或：|

    跟上面差不多，区别是或操作是只有两个位都为0时才为0，否则为1，比如：(1001 0011) | (0011 1101) = (1011 1111)

四、位异或：^

    异或就是，只有两个位不同的时候才为1，否则为0，比如：(1001 0011 ) ^ (0011 1101) = (1010 1110)

（位移位运算符）

五、左移：<<

    左移运算符将其左边的操作数的值的每一位向左移动，移动的位数由右边的操作数指定。比如：(0000 0011)<<2 = (0000 1100)。当然，如果移动的是无符号数，以上例子足以结束本节讨论，但涉及有符号数时，我们就要考虑更多的情况：

 

1、如果是无符号数 ，则向左移动n位时，丢弃左边n位数据，并在右边填充0 。参考以下代码：

 

---

int main(void){

    unsigned short i = 7;

    int j;

    for(j=1; j<17; j++){

        i = i<<1; // 将无符号数0x0007不断地左移。

        printf("i<<%02d = 0x%04hx = %d/n", j, i, i);

    }

    return 0;

}

---

 

打印结果如下：

注意中间那那一列十六进制表示的结果，可以清楚地看到，对于无符号数据而言，左移非常简单，不用考虑什么符号位，直到全部移除变成0拉倒。

 

2、如果是有符号数 ，则向左移动n位时，丢弃左边n位数据，并在右边填充0，同时把最高位作为符号位 。参考以下代码：

---

int main(void){

    short i = 7;

    int j;

    for(j=1; j<17; j++){

        i = i<<1; // 将有符号数0x0007不断地左移。

        printf("i<<%02d = 0x%04hx = %d/n", j, i, i);

    }

    return 0;

}

---

打印结果如下：

从结果可以清楚地看到，对于有符号数据的左移操作也非常简单，只不过要把最高位考虑成符号位而已，遇到1就是负数，遇到0就是正数，就是这么简单，直到全部移除变成0拉倒。

 

六、右移：>>

    对于右移操作来说，情况可能要稍微复杂一点，因为在右移有符号数的时候要考虑用什么来填充移走的左端的空位。当然对于无符号数而言，情况是非常明朗的，我们具体来看实验：

 

1、如果是无符号数 ，则向右移动n位时，丢弃右边n位数据，并在左边填充0 。参考以下代码：

---

int main(void){

    unsigned short i = 12288;

    int j;

    for(j=1; j<17; j++){

        i = i>>1; // 将无符号数12288（即二进制的0b0011 0000 0000 0000，这里我们用short只占用两个字节，方便书写而已）不断地右移。

        printf("i>>%02d = 0x%04hx = %d/n", j, i, i);

    }

    return 0;

}

---

打印结果如下：

从结果可以清楚地看到，对于无符号数据而言，右移很简单，也不用考虑什么符号位，左边填0补上，右边丢弃，直到全部移除变成0拉倒！

 

2、如果是有符号数 ，则向右移动n位时，丢弃右边n位数据，而左边填充的内容依赖于具体的机器，可能是1也可能是0 。

比如对于有符号数(1000 1010)来说，右移有两种情况：a) (1000 1010) >> 2 =(00 10 0010)；b) (1000 1010) >> 2 = (11 10 0010) 参考以下代码：

---

int main(void){

    short i = -12288;

    int j;

    for(j=1; j<17; j++){

        i = i>>1; // 将有符号数-12288（即二进制的0b1011 0000 0000 0000）不断地右移。

        printf("i>>%02d = 0x%04hx = %d/n", j, i, i);

    }

    return 0;

}

---

打印结果如下：

可见，我的机器（ubuntu-i386-9.04, gcc-4.3.3）上对于有符号数的右移操作属于第二种情况，最高的符号位保持原来符号位的一个副本不断右移，直到全部变成1拉倒！（12288写成二进制是0b0011 0000 0000 0000，-12288就是在此基础上取反加一：0b1100 1111 1111 1111 --> 0b1101 0000 0000 0000，这个数就是在存储器上实际存放的情况，右移一位后变成0b1110 1000 0000 0000，即上图中的0xe800）

 

当然，像我的机器这样左端填1来处理有符号数右移的情况，就是所谓的算术右移 ，如果右移时左端统统填0，则称之为逻辑右移 。

 

算术右移指令

算术右移指令SAR（shift arithmetic right）的操作是，将寄存器中的数值右移，最左端用最高位填充，而不是补零。这里分析它为什么不直接补零的原因。为方便讨论，考虑右移一位的情况。右移若干位的情况，也可做相似的分析。

不直接补零的根本原因是为了不改变数值的符号并且使得数值是原来的一半。众所周知，符号数是以补码的形式存储在计算机内的。正数的补码是其本身，最高位为0。 右移1位时，最高位补零，其值缩小一半。这没有什么问题。对于负数，其补码为对其绝对值求补后获得。最高位补1，也相当于次高位补1，能达到缩小一半的效果吗？那要看右移后对应的原码是否为原来的一半了。也就是，在最高位与次高位是不是0。要查看原码，只需对结果求一次补就行了。求补第一步是取反，这样填充的1就成了0，没有出现问题，但还得看第二步加1。哪些情况下加上1可能会影响次高位呢？答案只有两个数。当原来的补码除最高位与最低位都是0的时候，右移一位后除最高位外都是0，在求补进取反后这些0变成了1，加1后，进位会影响到次高位，使之变成1（经取反后，次高位被置成了0），而原码的次高位应该填充0的，这样就没有达到缩小原数的效果。以4位数为例，这样的数为：1000，1001。1000如果要计算机看成符号数的话，会被看成-16！而其它数，因为中间部分有1，取反后变成了0，加1后的进位不能影响到次高位，所有可以达到缩小原数且不改变符号的效果。

计算机求补的情形不多，一是指令中的数含有负号的时候，但如果指令中出现负0，也就是‘-0’汇编器会把它变成0。二是作减法运算的时候。

 

另外，我们平时编程的时候要习惯于这种高效的移位操作，事实上，移位操作跟加法操作一样，只需要一个指令周期（指令周期： 是CPU的关键指标，指取出并执行一条指令的时间。一般以机器周期为单位，分单指令执行周期、双指令执行周期等。现在的处理器的大部分指令（ARM、DSP）均采用单指令执行周期。机器周期： 完成一个基本操作的时间单元，如取指周期、取数周期。时钟周期： CPU的晶振的工作频率的倒数。 ），而乘法则需要数个指令周期，除法更甚。

我们可以用左移来表示任意整数的乘法，比如 n *= 8; 我们可以写成 n <<= 3; 而 n *= 13; 我们可以写成 n = (n<<3) + (n<<2) +n; 用左移来替代乘法不需要乘数是2的n次幂，但是用右移来替代除法的话，我们只能替代那些除数是2的n次幂的式子，比如 n /= 8; 我们可以写成 n >>= 3;

下面是指令ans = ans*13; 循环执行1亿次的时间统计：

这个是指令ans = (ans<<3) + (ans<<2) +ans; 循环执行1亿次的时间统计：

以上的三个时间分别是real墙上时间，user用户CPU时间，sys系统CPU时间。我们主要考察中间的user用户CPU时间 即可，它表示的是执行该用户进程指令所用的时间（real墙上时间是在当前系统负载下进程运行的时间总量，其值跟当前系统活动进程的数量有关；sys系统CPU时间是为该进程执行内核程序所经历的时间），可以看出，在不至于产生副作用的情况下，我们可以尽可能地用移位操作来代替乘法和除法，尤其在嵌入式开发中更应如此，虽然写出来的代码会稍微有一点点难读，但在效率面前我们应该加以权衡，对于大循环结构里面的语句更是这样，顺便说一句，写循环的时候要是脑袋里始终有一幅CPU流水线的运行图像就更牛了----尽量让你的循环配合处理器的流水作业，而不是破坏它，让处理器以更少的周期执行代码，提高效率。