位运算的常见操作和题目
最后更新于:2022-04-01 16:18:01
# 一、位运算基本操作
<table border="1" cellspacing="0" cellpadding="0" style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px"><tbody><tr><td valign="top"><p><span style="font-size:18px">& </span></p></td><td valign="top"><p><span style="font-size:18px"> 与 </span></p></td><td valign="top"><p><span style="font-size:18px">1 & 1 = 1;1 & 0 = 0;0 & 0 = 0 只有当两个位都为1时,结果为1</span></p></td></tr><tr><td valign="top"><p><span style="font-size:18px">| </span></p></td><td valign="top"><p><span style="font-size:18px"> 或 </span></p></td><td valign="top"><p><span style="font-size:18px">1 | 1 = 1;1 | 0 = 1;0 | 0 = 0 只有两个位都为0时,结果为0</span></p></td></tr><tr><td valign="top"><p><span style="font-size:18px">^ </span></p></td><td valign="top"><p><span style="font-size:18px">异或</span></p></td><td valign="top"><p><span style="font-size:18px">1 ^ 1 = 0;1 ^ 0 = 1;0 ^ 0 = 0 两个位相同时为0,相异时为1</span></p></td></tr><tr><td valign="top"><p><span style="font-size:18px">~ </span></p></td><td valign="top"><p><span style="font-size:18px">取反</span></p></td><td valign="top"><p><span style="font-size:18px">0变1,1变0</span></p></td></tr><tr><td valign="top"><p><span style="font-size:18px"><< </span></p></td><td valign="top"><p><span style="font-size:18px">左移</span></p></td><td valign="top"><p><span style="font-size:18px">各二进位全部左移若干位,高位丢弃,低位补0</span></p></td></tr><tr><td valign="top"><p><span style="font-size:18px">>> </span></p></td><td valign="top"><p><span style="font-size:18px">右移</span></p></td><td valign="top"><p><span style="font-size:18px">二进位全部右移若干位,<strong>对无符号数</strong>,高位补0;</span></p><p><span style="font-size:18px"><strong>有符号数</strong>,各编译器处理方法不一样,有的补符号位(算术右移),有的补0(逻辑右移)</span></p></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、 不借助变量交换两个数
具体查看文章:[不借助变量交换两个数](http://blog.csdn.net/u013074465/article/details/44342629)
### 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。
在文章[位操作实现加减乘除四则运算](http://blog.csdn.net/u013074465/article/details/42680239#t3)中的乘法操作就用到了本小结提到的这两个技巧。
### 5、32位系统某数右移/左移32位或更多位
在移位运算时,byte、short和char类型移位后的结果会变成int类型,对于byte、short、char和int进行移位时,规定实际移动的次数是移动次数和32的余数,也就是移位33次和移位1次得到的结果相同。
参考文章:[位移操作的另类情况](http://blog.csdn.net/u013074465/article/details/44645817)
# 三、位运算相关的题目
### 1、二进制中1的个数
用到了n & (n - 1)
(1)方法一:参考文章:[整数的二进制表示中1的个数](http://blog.csdn.net/u013074465/article/details/42617293)
方法二:[二进制位的翻转和二进制表示中1的个数](http://blog.csdn.net/u013074465/article/details/45485959)
(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、位操作实现加减乘除运算
[位操作实现加减乘除四则运算](http://blog.csdn.net/u013074465/article/details/42680239)
### 5、不借助变量交换两个数
参考文章:[不借助变量交换两个数](http://blog.csdn.net/u013074465/article/details/44342629)
### 6、比较两个数大小
参考文章:[不借助if、switch等语句求两个数较大的一个](http://blog.csdn.net/u013074465/article/details/42684559)
### 7、二进制位的翻转
[字符串合并处理(二进制位的倒序)](http://blog.csdn.net/u013074465/article/details/45485515)
[二进制位的翻转](http://blog.csdn.net/u013074465/article/details/45485959)
### 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对海量无重复的整数排序](http://blog.csdn.net/u013074465/article/details/46956295)
### 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。