ANSI-bit operation

位运算操作符(2.9 Bitwise Operators)

在C语言中提供了六种位运算操作符, 分别为: 按位取与(&), 按位取或(|), 按位取异或(^), 按位左移()和按位取反(~). 值得注意的是这些操作符只能用于操作整数的数据类型,不论其是有符号整数还是无符号整数. 进一步, 整数类型的数据类型为 char, short, int 和 long (根据在计算机内占据的字节多少排序). 至于浮点数, 由于位运算会直接操作二进制位, 因此可能会对浮点数的值造成难以预知的结果, 因此从语法层面直接禁止了对浮点数的位运算操作.

位运算操作符的含义

按位取与(&)

按位取与是将两个操作数的每位二进制互相进行取与操作, 如果两个操作数的对应位都为1, 那么结果的对应位为1, 否则为0. 例如: 1010 & 1100 = 1000. 值得注意的是, 按位取与大部分的用处实际上将某些位取0. 例如, 如果我们希望将某个数n的后7项保持不变, 其他位取0, 那么我们可以用按位取与完成这个操作

1 2	//将n的后7位保持不变, 其他位取0 n&0177

这里面我们用到了八进制的表示方法, 即以0开头的数字表示八进制数. 所以0177实际上在二进制上就是0000000001111111, 也就是后7位为1, 其他位为0. 因为任意数与0取与都是0,所以我们可以用这个把想要的位置置0.

小结一下, 按位取与的用途主要是将某些位取0, 保留某些位.

按位取或(|)

按位取或是将两个操作数的每位二进制互相进行取或操作, 如果两个操作数的对应位有一个为1, 那么结果的对应位为1, 否则为0. 例如: 1010 | 1100 = 1110. 因此, 按位取或的主要用途是将某些指定位置置1, 并保留其他位置的值不变. 例如, 如果我们希望将某个数的从右数第七位置为1, 其他位保持不变, 那么我们可以用按位取或完成这个操作.

1 2	//将n的第7位置1, 其他位保持不变 n\|0100

按位取异或(^)

按位取异或是如果两个操作数的对应位取值不同, 那么结果对应位就为1, 反之则为0. 例如, 1010¹¹⁰⁰=0110.

按位左移(<<)和按位右移(>>)

按位左移和右移操作是将左操作数的二进制位向左或向右移动右操作数指定的位数. 因此, 右操作数必须是一个非负整数. 例如, x<<2将x的二进制位整体向左移动两位, 并且在右边补0,这一操作的结果实际上是等价于对x乘4.但是右移操作并不能这么简单的总结, 因为右移操作会导致二进制高位的空缺, 因此如果我们考虑无符号整数的右移操作, 我们将二进制高位补0; 而如果我们考虑的是有符号整数的右移操作, 那就要与具体的底层代码实现有关:有的编译器会以符号位填补高位(算术移位), 有的编译器则会用0填补高位(逻辑移位).

按位取反(~)

与前面的几个操作符不同的是, 按位取反是一元操作符. 按位取反是将操作数的每一位取反, 即0变为1, 1变为0. 例如, ~1010=0101. 我们在按位取与中提到了将n的后几位保持不变, 其余位取0, 在此我们将用按位取与和按位取反来实现, 将n的后七位取0, 其余位保持不变:

1 2	//将n的后7位取0, 其余位保持不变 n&~0177

值得注意的是, 我们当然可以用 x&0177700 来实现这个操作, 但这其实相当于我们假定了x的位数就是16位, 显然这不适合代码的可移植性.

getbits 函数的设计思路与代码

getbits 函数功能

getbits 函数的形式为

1	unsigned int getbits(unsigned int x,int p,int n)

返回无条件整数x二进制形式从右边数第p位开始向右数n位的字段对应的unsigned int形式. 这里我们假设右边的第一位是第0位,n和p是合理的正值,输入错误处理暂时不考虑.

getbits 函数设计思路

因为我们需要从右边数第p位开始向右数n位的字段,所以这个字段最右边其实是第p+1-n位,因此我们需要将这个字段移动到最右边,我们可以用按位右移的方式将其移动到最右端,

1	x>>=(p+1-n);

接下来,我们需要导出最右边的n个字段,也就是相当于保持最右边n位不变,其余位置0即可.从前面的操作符,我们知道, 我们只需要让前面得到的结果和后n位为1, 其余位为0的数按位取与即可. 因此我们关注点就在于如何生成这个后n位为1, 其余位为0; 如果我们考虑将这个数取反, 那么我们只需要去构造后n位为0, 高位为1; 显然这个结果我们可以通过按位左移全1的数得到,所以我们将这个过程转换成代码得到

1
2
3

unsigned int y=~0;
y<<=n;
y=~y;

getbits 函数代码

Version 1

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

我们用操作符的优先级将上面的代码写的更加简洁得到Version2

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

Exercise 2-6

Exercise 2-6. Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged

函数设计思路

这个函数是要将x的中间一部分字段替换成y最右边的部分字段, 因此我们需要将y最右边的部分字段提取出来,然后向左移动到对应的位置,

1 2	unsigned int y1=y&(~(~0<<n)); y1<<=(p+1-n);

值得注意的是, 这里的y1只有中间一段是y最右边的部分字段, 其余为全是0, 然而我们需要用这个来覆盖掉x对应位置的字段, 保持其余位不变. 因此我们可以用按位取或来完成这个操作, 但值得注意的是这里我们是需要将x相应位置的字段置0. 这样我们就可以将x的相应位置的字段被y1覆盖,其余位不变.

//这一步是为了生成长为n的全1的字段数,其余数为0
unsigned int x1=((int)pow(2,n) - 1);
//左移p+1-n位,将其移动到对应的位置
x1<<=(p+1-n);
//x1此时是对应位置全1,其余位置为0,我们将其取反,得到对应位置全0,其余位置全1
x1=~x1;
//最后我们将x相应的字段置0,其余位置保持不变
x&=x1;

代码实现

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

Exercise 2-7

Write a function invert(x,p,n) that returns x with the n bits that begin at position p inverted (i.e., 1 changed into 0 and vice versa), leaving the others unchanged

函数设计思路

我们的思路其实就是先将x的指定字段提取出来, 然后只对这一部分取反,再重新取代x相应位置的字段即可. 第一步, 提取x的指定字段, 我们已在getbits函数给出了; 接下来, 我们假设取出来的字段为y, 接下来我们需要对y的字段取反, 但是值得注意的是我们不能将y的高位取反, 换言之, 我们只改变y的右边n位二进制的值, 我们用按位取异或的方式来处理.

1	y=y^((int)pow(2,n)-1);

最后我们就回归了2-6的问题.

代码实现

unsigned int invert(unsigned int x, int p, int n)
{
  //将x的指定字段提取出来
  unsigned int temp=(x>>(p+1-n))&~(~0<<n);
  //将temp最右边n位数取反
  temp^=((int)pow(2,n)-1);
  //将temp重新取代x相应位置的字段
  return (temp<<(p+1-n))|(x&~(((int)pow(2,n)-1)<<(p+1-n)));
}

Exercise 2-8

Write a function rightrot(x,n) that returns the value of the integer x rotated to the right by n positions.

函数设计思路

两个思路：

用循环的方式, 每次我们都将x的最右边的一位取出来，然后将x右移一位, 将取出来的位放到最左边, 重复n次即可. 因为这些技术细节其实都在前面解释过了, 这里我们就不去解释了.
这一种则是,我直接一次性将x的最右边n位取出来, 然后将x右移n位, 将取出来的n位放到最左边即可.

但是这两个方法有一个问题,就是我们必须知道x本身在计算机占用的位数, 不然的话, 我们没法移动到合适的位置. 但我们可以通过按位右移的方式来解决这个问题, 假设x占用了4个二进制位, 我们将其按位右移四次, 那么x就变成了0, 因此我们就得到了x的位数

代码实现

思路一

unsigned rightrot(unsigned x, int n)
{
        int length = len(x);
        for (int i = 1; i <= n; i++)
        {
                unsigned temp = (x & 1) << (length - 1);
                x = (x>>1) | temp;
        }
        return x;
}

思路二

unsigned rightrot(unsigned x, int n)
{
        int length = len(x);
        unsigned int temp=x&~(~0<<n);
        x=x>>n;
        temp=temp<<(length-n);
        x=x|temp;
        return x;
}

获得x的位数的函数程序

int len(unsigned x)
{
        int i = 0;
        for (; x != 0; x >>=1)i++;
        return i;
}