位运算的常见操作和题目

傷城~ 2022-08-01 15:44 202阅读 0赞

# 一、位运算基本操作 #

<table style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px"> 
 <tbody> 
 <tr> 
 <td> &amp; &nbsp; &nbsp; &nbsp; &nbsp; </td> 
 <td> &nbsp;与 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; </td> 
 <td> 1 &amp; 1 = 1；1 &amp; 0 = 0；0 &amp; 0 = 0 &nbsp;只有当两个位都为1时，结果为1 </td> 
 </tr> 
 <tr> 
 <td> |&nbsp;&nbsp; </td> 
 <td> &nbsp;或&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td> 1 | 1 = 1；1 | 0 = 1；0 | 0 = 0 &nbsp; 只有两个位都为0时，结果为0 </td> 
 </tr> 
 <tr> 
 <td> ^&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td> 异或 </td> 
 <td> 1 ^ 1 = 0；1 ^ 0 = 1；0 ^ 0 = 0 &nbsp; 两个位相同时为0，相异时为1 </td> 
 </tr> 
 <tr> 
 <td> ~&nbsp;&nbsp;&nbsp; </td> 
 <td> 取反 </td> 
 <td> 0变1，1变0 </td> 
 </tr> 
 <tr> 
 <td> &lt;&lt;&nbsp; </td> 
 <td> 左移 </td> 
 <td> 各二进位全部左移若干位，高位丢弃，低位补0 </td> 
 </tr> 
 <tr> 
 <td> &gt;&gt;&nbsp; </td> 
 <td> 右移 </td> 
 <td> 二进位全部右移若干位，对无符号数，高位补0； 有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移） </td> 
 </tr> 
 </tbody> 
</table>

1、以上运算符，仅~是单目运算符，其他都是双目运算符。

2、位操作仅针对整型数据，对float、double进行位操作会出错。

3、VS2010 和GCC均采用算术右移：对负数右移，会在其高位补符号位，也就是补1。

4、还有其他复合位操作： &= |= <<= >>=

# 二、位操作的运用 #

## 1、奇偶性的判断 ##

对于二进制表示来说，其最右位为1则该数为奇数，最右位为0则该数为偶数。

int a;
 cin >> a;
 if (a & 1)
 cout << "奇数" << endl;
 if ((a & 1) == 0) //注意：&的优先级低于==的优先级，因此if内部与运算必须加括号！
 cout << "偶数" << endl;

## 2、 不借助变量交换两个数 ##

具体查看文章：[不借助变量交换两个数][Link 1]

## 3、取相反数 ##

也就是将正数n变为-n，将负数n变为-n。

将整数**取反加1**即可得到其相反数：

例如，32位系统中正数13（二进制表示为00000000 00000000 00000000 00001101），

**取反**为（11111111 11111111 11111111 11110010），

然后再加1为（11111111 11111111 11111111 11110011），计算机中数是用二进制的补码表示的，

因此取反加1的结果（11111111 11111111 11111111 11110011）即为-13的二进制补码表示形式。

常见的一个等式：\-n = ~(n - 1) = ~n + 1

例子：求某整数的绝对值：

//求某整数的绝对值
 int my_abs(int number) {
 	if (number < 0) {
 		return ~number + 1; //或return -number; 或return ~(n - 1)
 	}
 	return number;
 }

## 4、整数二进制表示中最右边的1 ##

**获取整数二进制表示中最右侧的1：n & (-n) 等价于 n & ~(n - 1) 。**

例如，n = 1100， -n = 0100， 那么n & (-n) = 0100，这样就获取到了二进制表示中最右侧的1。

**去除整数二进制表示中最右侧的1：n & (n - 1)**

例如，n = 1100，n - 1 = 1011，那么n & (n - 1) = 1000，这样就去除了二进制表示中最右侧的1。

在文章[位操作实现加减乘除四则运算][Link 2]中的乘法操作就用到了本小结提到的这两个技巧。

## 5、32位系统某数右移/左移32位或更多位 ##

在移位运算时，byte、short和char类型移位后的结果会变成int类型，对于byte、short、char和int进行移位时，规定实际移动的次数是移动次数和32的余数，也就是移位33次和移位1次得到的结果相同。

参考文章：[位移操作的另类情况][Link 3]

# 三、位运算相关的题目 #

## 1、二进制中1的个数 ##

用到了n & (n - 1)

(1)方法一：参考文章：[整数的二进制表示中1的个数][1]

方法二： [二进制位的翻转和二进制表示中1的个数][1 1]

(2) **输入两个数A和B，输出将A转换为B所需改变的二进制的位数**。

方法：首先，A异或B得到的是A和B中不相同位数组成的数，然后再求这个数二进制表示中1的个数，即为所求。

## 2、数组中只出现一次的数字 ##

用到了n & (n - 1)

数组中仅出现一次的一个数字、仅出现一次的两个数字

参考文章：[http://zhedahht.blog.163.com/blog/static/2541117420071128950682/][http_zhedahht.blog.163.com_blog_static_2541117420071128950682]

数组中仅出现一次的三个数字

参考文章：[http://zhedahht.blog.163.com/blog/static/25411174201283084246412/][http_zhedahht.blog.163.com_blog_static_25411174201283084246412]

## 3、不用加减乘除做加法 ##

参考文章：[http://zhedahht.blog.163.com/blog/static/254111742011125100605/][http_zhedahht.blog.163.com_blog_static_254111742011125100605]

## 4、位操作实现加减乘除运算 ##

[位操作实现加减乘除四则运算][Link 4]

## 5、不借助变量交换两个数 ##

参考文章：[不借助变量交换两个数][Link 1]

## 6、比较两个数大小 ##

参考文章：[不借助if、switch等语句求两个数较大的一个][if_switch]

## 7、二进制位的翻转 ##

[字符串合并处理（二进制位的倒序）][Link 5]

[二进制位的翻转][1 1]

## 8、二进制表示的高低位交换 ##

[http://blog.csdn.net/morewindows/article/details/7354571][http_blog.csdn.net_morewindows_article_details_7354571]

## 9、位操作与空间压缩 ##

[http://blog.csdn.net/morewindows/article/details/7354571\#t6][http_blog.csdn.net_morewindows_article_details_7354571_t6]

## 10、bitmap对海量数据排序 ##

[bitmap对海量无重复的整数排序][bitmap]

## 11、求两个数中较小的那个 ##

y ^ ((x ^ y) & -(x < y))

分析：当x < y时，-(x < y)为-1，其补码形式全为1，则(x ^ y) & -(x < y) = x ^ y，则上述表达式返回的是较小的数x；

当x >= y时，-(x < y)为0，补码形式为全0，则(x ^ y) & -(x < y) = 0， 则表达式返回的是较小的数y。

[Link 1]: http://blog.csdn.net/u013074465/article/details/44342629
[Link 2]: http://blog.csdn.net/u013074465/article/details/42680239#t3
[Link 3]: http://blog.csdn.net/u013074465/article/details/44645817
[1]: http://blog.csdn.net/u013074465/article/details/42617293
[1 1]: http://blog.csdn.net/u013074465/article/details/45485959
[http_zhedahht.blog.163.com_blog_static_2541117420071128950682]: http://zhedahht.blog.163.com/blog/static/2541117420071128950682/
[http_zhedahht.blog.163.com_blog_static_25411174201283084246412]: http://zhedahht.blog.163.com/blog/static/25411174201283084246412/
[http_zhedahht.blog.163.com_blog_static_254111742011125100605]: http://zhedahht.blog.163.com/blog/static/254111742011125100605/
[Link 4]: http://blog.csdn.net/u013074465/article/details/42680239
[if_switch]: http://blog.csdn.net/u013074465/article/details/42684559
[Link 5]: http://blog.csdn.net/u013074465/article/details/45485515
[http_blog.csdn.net_morewindows_article_details_7354571]: http://blog.csdn.net/morewindows/article/details/7354571
[http_blog.csdn.net_morewindows_article_details_7354571_t6]: http://blog.csdn.net/morewindows/article/details/7354571#t6
[bitmap]: http://blog.csdn.net/u013074465/article/details/46956295