快速了解所有位运算：[&] [|] [^] [~] [＜＜] [＞＞]
快速了解所有位运算：[&] [|] [^] [~] [＜＜] [＞＞]
位运算在计算机编程中是一种非常基础且重要的运算方式，它直接操作数据的二进制位，可以实现一些高效且巧妙的算法。本文将详细介绍六种基本的位运算操作：按位与(&)、按位或(|)、按位异或(^)、按位取反(~)、左移(<<)和右移(>>)。并通过两个实际的编程题目，帮助读者更好地理解和应用这些运算。
一、位运算介绍
注意：位运算都是基于数的二进制表示来计算的，所以以下示例，都是二进制数为例进行。
&（按位与）
- 说明：两个都是1才为1，否则0.
- 示例1：1100&1110=1100
- 示例2：1111&0000=0000
- 常用性质：
- 任何数 x 与0进行与运算都得0：x & 0 = 0
- & 操作满足交换律：x & y = y & x
- & 操作满足结合律：(x & y) & z = x & (y & z)
|（按位或）
- 说明：只要有1，结果就是1，否则为0.
- 示例1：1111|0000=1111.
- 示例2：0110|0100=0110.
- 常用性质：
- 任意数 x 和0进行或运算结果为 x ：x | 0 = x
- 任何数 x 与 -1 进行 | 操作结果为 -1 ：x | -1 = -1
- | 操作满足交换律：x | y = y | x
- | 操作满足结合律：(x | y) | z = x | (y | z)
^（按位异或）
- 说明：相同为0，相异为1.
- 示例1：1111|0001=1110.
- 示例2：0110|0100=0010.
- 性质：
- 任意数 x 和 0 进行异或，结果为 x ：x ^ 0 = x
- 两个相同的数 x 进行异或运算结果为 0 ：x ^ x = 0
- ^ 操作满足交换律：x ^ y = y ^ x
- ^ 操作满足结合律：(x ^ y) ^ z = x ^ (y ^ z)
~（按位取反）
- 说明：是1，则为0，是0则为1.（注意 ~ 是单目运算符）
- 示例1：~1010=0101
- 示例2：~0110=1001.
- 常用性质：
- ~ 是自反操作，连续两次取反结果为原数：~~x = x
>>（右移运算符）
- 说明：向右移动x位，高位补0.
- 示例1：1111>>3=0001.(3是十进制数，代表右移3位)
- 示例2：0110>>1=0011.（1是十进制数，代表右移1位）
- 常用性质：右移等价于除法（在没有溢出的情况下）：x ≫ n ⟺ x 2 n x \gg n \iff \frac{x}{2^n}x≫n⟺2nx
x ≫ 1 ⟺ x 2 x \gg 1 \iff \frac{x}{2}x≫1⟺2x 最常用
<<（左移运算符）
- 说明：向左移动x位，低位补0.
- 示例1：1111<<3=1000.(3是十进制数，代表左移3位)
- 示例2：0110<<1=1100.（1是十进制数，代表左移1位）
- 常用性质：左移等价于乘法（在没有溢出的情况下）:x ≪ n ⟺ x × 2 n x \ll n \iff x \times 2^nx≪n⟺x×2n
x ≪ 1 ⟺ x × 2 x \ll 1 \iff x \times 2x≪1⟺x×2最常用
二、练习题
习题1（>>和&）
1、题目描述
力扣题目连接
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
- 示例 1：
输入:s = “leetcode”
输出:false - 示例2：
输入:s = “abc”
输出:true - 限制：
- 0 <= len(s) <= 100
- s[i]仅包含小写字母
- 如果你不使用额外的数据结构，会很加分。
2、题目解析
这是一道FaceBook的一道经典面试题，解法很多，如果使用了巧妙地解法，就很加分。所以本道题目我们用位运算来解决。
题目已经说明，给定的字符只能是小写字母这才26个呀。
那我们可以先用26个标志位：
然后遍历每一个字符，把字符对应的下标位置的值+1：
在遍历完所有字符后，判断这个集合中的元素是否有大于1的，如果有，说明出现了重复的字符；如果没有大于1的元素，说明字符都是单个出现的。
那么这个位运算有什么关系呢？
实际上，图中的集合可以直接用一个26位的二进制数binary来表示，初始值为0：
binary=0000 0000 0000 0000 0000 0000 00
每当遍历到一个字母（假设这个字母对应的序号是x），那么我们就binary>>x ，然后判断当前binary的最低位是否是1。如果不是1，我们就可以通过binary|=1<<x ，来将binary的对应位置设置成1；如果是1，说明之前出现了相同的字母，那么直接返回假即可。
示例（模拟重复出现两个’b’字符的情况）：
3、AC代码（java）
class Solution {
public boolean isUnique(String astr) {
//注意如果所给的字符串大于26个，说明肯定有重复的
if(astr.length()>26)return false;
int t=0;
for(int i=0;i<astr.length();i++){
//获取对应字母的序号x
int x=astr.charAt(i)-'a';
//判断之前这个位置的字母是否已经出现过（置为1）
if(((t>>x)&1)==1)return false;
//没有出现过，对应位置置为1
t|=1<<x;
}
return true;
}
}
习题2（|和^）
蓝桥云课题目连接
题目描述：
题目解析
简要说明题目大意：求一个最小值 x ，且 x 必须满足 a|x = b|x 。
题意简单，但是乍一看好像没有什么思路。但是它考的可是位运算啊，那我们就从二进制数入手，假设a、b两个数的二进制数的某一位为0或者1，推导x对应位的值：
- a=0 b=0：
a|1=1，b|1=1，所以x可以是1
a|0=0，b|0=0，所以x也可以是0，但是题目希望x是最小值，所以 x=0 - a=1 b=1：
a|1=1，b|1=1，所以x可以是1
a|0=0，b|0=0，所以x也可以是0，但是题目希望x是最小值，所以 x=0 - a=1 b=0：
a|1=1，b|1=1，所以x可以是1
a|0=1，b|0=0，两值不等，所以 x=1 - a=0 b=1：
a|1=1，b|1=1，所以x可以是1
a|0=0，b|0=1，两值不等，所以 x=1 - 总结：
我们发现 a=b=0 或者 a=b=1 ，那么 x=0 。如果 a!=b ，那么 x=1 。大家有没有发现规律呢？
实际上这就是 ^ （按位异或）运算的规律，相同为 0 ，相异为 1 。
那么解题方法就水落石出了，直接对a和b进行 ^ 运算即可！
AC代码(Java)
import java.util.Scanner;
public class 最小的或运算 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print(sc.nextLong() ^ sc.nextLong());
}
}