位运算应用

喜欢ヅ旅行 2022-05-10 04:48 272阅读 0赞

## &与运算应用 ##

![与运算应用][70]

## 按位或| ##

![在这里插入图片描述][70 1]

## 异或运算^ ##

![在这里插入图片描述][70 2]  
![在这里插入图片描述][70 3]

## 取反运算~ ##

![在这里插入图片描述][70 4]

## 左移运算<< ##

![在这里插入图片描述][70 5]

## 右移运算>> ##

![在这里插入图片描述][70 6]

## 无符号右移运算>>> ##

![在这里插入图片描述][70 7]  
负数以其正值的补码形式表示  
![在这里插入图片描述][70 8]  
![在这里插入图片描述][70 9]

![在这里插入图片描述][c-bit-all.png]

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=1020b=ab=(1020)20=102020=100=10a=ab=102010=101020=0^20=20把上述代码，可以封装为一个交换2个数的函数如下： 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)+11<<2+3解答：(char)(127<<1)+1=(01111111<<1)+1=11111110+1=11111111=-1(char)(-1>>1)+1=(11111111>>1)+1=11111111+1=01<<2+3=1<<(2+3)=1<<5=2^5=32(注意《和+的优先级）

--------------------

本文来自 iris\_gril 的CSDN 博客 ，全文地址请点击：[https://blog.csdn.net/u012713968/article/details/50481680?utm\_source=copy][https_blog.csdn.net_u012713968_article_details_50481680_utm_source_copy]

关于位运算的一点总结：  
很久之前借了学校图书馆的一本叫做算法心得的书，看过之后感觉作者简直神奇，不愧是大师，里面是各种优化程序的奇淫技巧，不过那时什么都不懂，看了觉得没用，现在懂了一点了，然而之前看过的都忘了，里面关于位运算的内容特别多，值得一看。  
下面就是一些常见的技巧，效率都比普通运算要高很多

/*1、交换两个整数的值：int a, b;a = a ^ b;b = a ^ b;a = a ^ b;与下面的等价,不过利用的是^的重要性质，效率当然比算术运算高a = a + b;b = a - b;a = a - b;2、与2的x次方的运算int a;a <<= x;//乘2^xa >= x;//除2^xa & (1 << x) - 1 //取a%(2^x)的余数a & 1//判断奇偶性，为0则a为偶数,否则为奇数a & (a-1)//判断a是否为2的幂或者0，结果为0代表是，否则代表不是3、其他常用技巧int a, b;a = ~a + 1//取相反数a = (a ^ (a >> 31)) - (a >> 31) //取绝对值(a & b) + ((a ^ b) >> 1) //取平均值a ^ b//判断a、b符号是否相同，如果结果>0则相同，否则不同*/

(1)、位运算优先级较低，如果结合其他的运算符，那么最好在使用时加上括号，当然如果很清楚优先级就另当别论了。  
(2)、位运算虽说高效，但是很多枚举子集的技巧数据量大点就无法使用了，所以还是得慎用，根据题目的数据范围而定吧。  
(3)、使用位运算注意细节的处理，比如说枚举子集时的起点，终点等等。  
(4)、使用位运算关键是理解每一个运算的特点，灵活运用它们的性质，并且找到问题与位之间的联系，其实上面的几个枚举集合的技巧都是根据位之间的联系然后运用相应的运算符得出的，一些位运算符也有一些非常重要的特点，比如说异或运算具有交换律，结合律，自反性等等。  
(5)、位运算应用很广，体现在很多算法和数据结构上，比如说状态压缩，树状数组等等，在状态压缩中的使用通常是最常见的，很多算法都设计到状态之间的转移，比如说搜索，dp等等。有时候很难表示当前的这个状态，但是通过二进制位便可以解决了，所以位运算还是很方便和实用的，比如说一些在棋盘，网格中要表示某一行/列的状态时的问题。  
在数据结构中的应用最常见的是树状数组，借用论文上面的话：树状数组的思想核心在于运用了十进制数与二进制数之间的联系，通过数的二进制形式来决定储存信息，把复杂的问题简单化,方法简单巧妙。  
树状数组的优势在于代码长度短，不易出错，思想巧妙，算法复杂度低，维护简单，易推广到二维甚至三维等等。对于数据结构要求操作不复杂的题目，是上佳的选择。  
而且线段树也涉及到了简单的右移位运算，或运算等等。

--------------------

本文来自 HopeForBetter 的CSDN 博客 ，全文地址请点击：[https://blog.csdn.net/consciousman/article/details/52825345?utm\_source=copy][https_blog.csdn.net_consciousman_article_details_52825345_utm_source_copy]

[70]: /images/20220510/a8d2aadd5eff4db49569da3480a9db5c.png
[70 1]: /images/20220510/f5e263708510450089fa2c171a576057.png
[70 2]: /images/20220510/a6bbdb4885cb48eca7f4c83241495cdf.png
[70 3]: /images/20220510/0a786b0037e7406ab29ceaea8e29c474.png
[70 4]: /images/20220510/72dc62213f23472f88a4a87b520f2f2a.png
[70 5]: /images/20220510/391647cadf0d4a9787f78d5ca3233005.png
[70 6]: /images/20220510/382e9688ad8c4f63beeab262f9b41b01.png
[70 7]: /images/20220510/3e58de70f1eb4eed8ddd2ff6da991e6f.png
[70 8]: /images/20220510/8ca2f20a73934acf9ffa5a446d945c28.png
[70 9]: /images/20220510/539ddb3f8c15456facbde695d0f0d1ef.png
[c-bit-all.png]: /images/20220510/5b4811d89b5b43c39859165e0de97f9a.png
[https_blog.csdn.net_u012713968_article_details_50481680_utm_source_copy]: https://blog.csdn.net/u012713968/article/details/50481680?utm_source=copy
[https_blog.csdn.net_consciousman_article_details_52825345_utm_source_copy]: https://blog.csdn.net/consciousman/article/details/52825345?utm_source=copy