C语言位操作

最近在重新学习C语言，使用的书为Brian W.Kernignan 和 Dennis M.Ritchie的《C程序设计语言》。今晚读到了位操作，并写了一些简单的测试程序。

C语言提供了6个位操作运算符。这些运算符只能作用于整型操作数，即只能作用于带着有符号或无符号的char、short、int与long类型。

这六种位操作运算符为：

&     按位与
|      按位或
^     按位抑或
<<   左移
>>   右移
~     按位求反

位操作常用于一些开关性质的操作。例如：

x = x | SET_ON

就可以用来表示置某一位为1，假如置第3位（从左边数，第一位为0）为1，则SET_ON = 0100

若要置某一位为0，则

x = x & SET_OFF

若同样将第三位置0，则SET_OFF = 1011

关于按位求反的一个比较特殊的用法是：

x = x & ~077

将x的最后6位置0。表达式~077与机器字长无关，他比形式0177700的表达式要好，因为后者假定x是16位的数值。这种可移植的形式并没有增加额外开销，因为~077是常量表达式，可以在编译时求值。

在对unsigned类型的无符号值进行右移位时，左边空出的部分将用0填补；当对signed类型的带符号值进行右移时，某些机器将对左边空出的部分用符号为填补（即“算术运算”），而另一些机器则对左边空出的部分用0填补（即“逻辑移位”）。

下面介绍几个使用位操作的实例：

1、编写函数getbits(x,p,n)，它返回x中从右边数第p位开始向右数n位的字段。这里假定最右边的一位是第0位，n与p都是合理的正值。

此题为该书的实例程序，不再过多介绍，代码如下：

unsigned getbits(unsigned x,int p,int n)
{
    return (x >> (p + 1 - n)) & ~(~0 << n);
}

2、编写一个函数setbits(x,p,n,y)，该函数返回对x执行下列操作后的结果值：将x中从p位开始的n个（二进制）位设置为y中最右边n位的值，x的其余各位保持不变

如上图所示，首先将x 与 ~(~(~0 << n) << (p + 1 - n))相与，清零x的左边第p位向右n位，得到结果1。

其次，将y与~(~0 << n) 相与以清零y除0到n-1的位，在上述结果左移p + 1 - n 位，即将y的低n位左移，得到结果2

最后将结果1与结果2或，则得到结果，代码如下：

unsigned setbits(unsigned x, int p, int n, unsigned y)
{
    return ~(~(~0 << n) << (p + 1 - n)) & x | ((~(~0 << n) & y) << (p + 1 - n));
}

3、编写一个函数invert(x,p,n)，该函数返回对x执行下列操作后的结果值：将x中从第p位开始的n个（二进制）位求反，x的其余位保持不变

此题就不再画图了，直接说明思路即可

若使用按位求反，则就将x的每一位求反，不符合要求。值得注意的是异或^操作，0与1异或的结果是1,1与1异或的结果是0，可见与1异或的结果便是对该位求反。另外0与0异或的结果是0,1与0异或的结果还是1,，可见与0异或的结果是保持自己不变。利用此特性可以解决该题目。即让x与类似于000011110000（可表达为~(~0 << n) << (p + 1 - n)的值异或。代码如下：

unsigned invert(unsigned x, int p, int n)
{
    return x ^ (~(~0 << n) << (p + 1 - n)); 
}

4、编写一个函数rightrot(x,n)，该函数返回将x循环右移（即从最右端移出的位将从最左端移入）n（二进制）位后所得到的值

基本的左移与右移函数，与移位方向相反的一端一般补充0或符号位，无法达到循环移位的目的。为了达到循环移位，可以将x的最右边n位首先左移至最左边，然后将x右移n位，将两结果进行或操作即可。代码如下：

unsigned rightrot(unsigned x, int n)
{
    unsigned l = sizeof(x) * 8;
    n %= l;
    return (~(~0 << n) & x) << (l - n) | x >> n;
}

5、最后介绍一种求一个整数x的二进制中1的个数的方法。

最直接暴力的方法就是直接将x的二进制表示计算出来，然后数一数1的个数。但还有一个更“聪明”的方法。

要理解更“聪明”的想法，首先需清楚 x & (x - 1)的结果所表达的含义。此操作会将x的二进制中最右边的一个1变成0。至于为什么，读者可以自己思考。

这样就很容易的写出代码了：

unsigned bitcount(unsigned x)
{
    int i = 0;
    for(; x != 0;x &= (x - 1))
        ++i;
    return i;
}

上述的5个题目中涵盖了C语言中六种位操作的基本使用方法。学习使用位操作不仅仅是学习位操作，我更觉得通过此种学习方法可以锻炼自己的逻辑思维，加强自己对逻辑的敏感度。

PS：完成上述的几个函数时，几次都掉进了坑里。这个坑就是运算符的优先级问题。位运算符的优先级是低于加（+）减（-）操作符的。故 x << n + 1指的是x左移n+1位，而不是x左移n位再加1。刚开始尝试编写上述几个函数时，使用了加法，后经思考将加法替换成了或操作。