标题:位运算与应用


一,位运算基础


位运算(包括与,或,取反,异或,左移,右移等)是程序设计中的一个重要的领域。尤其是安全和底层开发中,除了指针的频繁使用之外,位运算是另一个非常频繁使用的领域。 因此,在求职面试中,位运算也是每年重点考查的知识点。首先,我们有必要复习一下C语言中位运算的一些基础计算方法。
 
1,与运算:&

与运算的操作符为&。2个数进行与运算时,就是将这2个数的二进制进行与操作, 只有当2个数对应的位都为1,该位运算结果为1,否则运算结果为0。即:1&1=1;1&0=0;0&0=0.
比如计算15&10,首先15的二进制为:1111,10的二进制为1010(二进制,十进制和十六进制转化方法:点击这里),所以15&10为:
所以15&10=10。

2,或运算:|


或运算的操作符为|。2个数进行或运算时,就是将这2个数的二进制进行或操作, 只要2个数对应的位有一个为1,该位运算结果为1,否则运算结果为0。即:1|1=1;1|0=1;0|0=0.
比如计算15&10,首先15的二进制为:1111,10的二进制为1010,所以15|10为:
所以15|10=15。

3,取反运算:~


取反运算的操作符为~,为单目运算符。取反运算符顾名思义,就是将一个整数中位为1的变成0,位为0的变成1。即:~1=0;~0=1.
比如计算~10,首先10的二进制为:1010,~10为:
~10=5。

 
4,异或运算:^

异或运算的操作符为^。2个数进行异或运算时,就是将这2个数的二进制进行异或操作, 只要2个数对应的位相同,该位运算结果为0,否则运算结果为1。即:1^1=0;1^0=1;0^0=0.
比如计算15^10,首先15的二进制为:1111,10的二进制为1010,所以15^10为:
所以15^10=5。

5,右移运算符:>>

右移运算符为>>。将一个数a向右移动n位记为:a>>n。比如将12向右移动2位如何计算呢?12的二进制为00001100,那么右移动2位为:00000011,即3。 即12>>2为3。

右移动运算分为两种右移,一种为逻辑右移,在移动过程中,左边位用0填充。一种为算术右移,在移动过程中,左边用符号位来填充。 比如对于有符号数:10000011,对于逻辑右移,向右移动3位,那么左边用0填充,变成了:00010000。而对于算术右移,向右移动3位,那么左边用1(1为符号位)填充,变成了11110000。而对于01000011,算术右移3位,那么左边用0(0为符号位)填充,变成了00001000。 在C语言中,右移运算符为算术右移运算符,即左边用符号位来填充。

6,左移运算符:《

左移运算符为《。将一个数a向左移动n位记为:a《n。 比如将12向左移动2位如何计算呢?12的二进制为00001100,那么左移动2位为:00110000。 无论左移还是右移,都需要用0或者1去填充移动之后空位。在左移的过程中,右边一律用0去填充。左移就没有右移那样分为逻辑右移和算术右移。 比如,将10左移2位,由于10的二进制为:00001010,那么左移2位,右边用零填充的结果为:00101000。 将一个数左移N位相当于将一个数乘以2^N,而将一个数右移N位相当于将这个数除以2^N。

位运算运算符的优先级如下:(优先级由高到低排列)
而所有的C运算符的优先级与结合律如下图:(从图中可以看出,算术运算符的优先级高于《和》运算符)
一些常见的二进制位的变换操作如下图:

在实际的编程过程中,往往会用一个整数的不同位表示不同的数据信息。在访问该整数时,就需要通过位运算来获得或者改变整数的某几位数值。比如在Windows中创建文件时使用的Create数据结构:
struct
{
     PIO_SECURITY_CONTEXT SecurityContext;
    ULONG Options;
    USHORT POINTER_ALIGNMENT FileAttributes;
    USHORT ShareAccess;
    ULONG POINTER_ALIGNMENT EaLength;
    PVOID EaBuffer;
    LARGE_INTEGER AllocationSize;
 } Create;
通常会引用其中的Options如下:
Data->Iopb->Parameters.Create.Options
ULONG Options是一个Windows文件创建过程中的无符号长整数,指示在创建和打开文件时的不同选项。其中高8位指示了CreateDisposition参数(如FILE_OPEN,FILE_CREATE),低24位指示了CreateOptions参数(如FILE_DELETE_ON_CLOSE)。 为了得到CreateDisposition的值,采取下面的位操作:
 (Data->Iopb->Parameters.Create.Options >> 24) & 0x000000ff;
将该整数右移24位,再与0xff做与操作,即可获得CreateDisposition的值。
 

二,位运算应用

1.任何一个数和0异或是它的本身,和自身异或为0:

a^0=a
a^a=0
利用上述性质,可以用来计算2个数的交换。
大家应该知道,在计算机里,两个数互相交换,需要定义一个中间的变量来参与交换。如:
int tmp;
int a=10;
int b=20;
tmp=a;
a=b;
b=tmp;
上述代码计算之后,a和b的值完成交换,a的值为20,b的值为10。
如果用异或运算来交换2个数,可以如下方法:
int a=10;
int b=20;
a=a^b;
b=a^b;
a=a^b;
上述运行之后,a和b依然完成了值的交换,但由于是异或位运算,所以效率比上面的代码要高。
证明:
a=10^20
b=a^b=(10^20)^20=10^20^20=10^0=10
a=a^b=10^20^10=10^10^20=0^20=20
把上述代码,可以封装为一个交换2个数的函数如下:
void swap(int *a, int *b)
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
 }
或者用宏来定义:
#define SWAP(a,b) \
do { \
     a = a^b; \
     b = a^b; \
     a = a^b; \
} while(0)
但按照下面的方法来写一个函数,试着将两个数进行交换,是错误的(想想为什么?)
void swap(int a, int b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
 }
2.将整数的第n位置位或清零:

#define BITN (1《n)
置位:a |= BITN;
清零:a &= ~BITN

3.清除整数a最右边的1。

方法:a & (a – 1)//该运算将会清除掉整数a二进制中最右边的1。
问题:如何判断判断整数x的二进制中含有多少个1?
分析:此题是微软公司的一道笔试题。下面用&运算来解决此题。 代码如下:
int func(int x )
{
    int countx = 0;
    while ( x )
    {
        countx++;
        x = x&(x-1);
    }
    return countx;
}
4.用异或运算设计一个只有一个指针域的双向链表:

 

提示:
要实现该设计要求,需要记住链表的头结点和尾结点,并在链表结点的的next域存放前一个结点和后一个结点的异或值。即:
p->next=pl^pr;//头结点的左边结点为NULL,尾结点的右边结点为NULL。
在遍历的时候,从头结点往右遍历的方法:
pl=NULL;
p=Head;
while(p!=Tail)
{
    pr=pl^(p->next);
    pl=p;
    p=pr;
 }
从尾结点往左遍历的方法:
pr=NULL;
p=Tail;
while(p!=Tail)
{
    pl=pr^(p->next);
    pr=p;
    p=pl;
}

5.计算下面表达式的值

(char)(127<<1)+1
(char)(-1>>1)+1
1<<2+3

解答:
(char)(127<<1)+1=(01111111<<1)+1=11111110+1=11111111=-1
(char)(-1>>1)+1=(11111111>>1)+1=11111111+1=0
1<<2+3=1<<(2+3)=1<<5=2^5=32(注意《和+的优先级)



看文字不过瘾?点击我,进入腾讯课堂视频教学
麦洛科菲长期致力于IT安全技术的推广与普及,我们更专业!我们的学员已经广泛就职于BAT360等各大IT互联网公司。详情请参考我们的 业界反馈 《周哥教IT.C语言深学活用》视频

我们的微信公众号,敬请关注