1.位运算
1.二进制数值表示
在计算机中，我们可以用单纯的0和1来表示数字，一般不产生歧义，我们会在数字的右下角写上它的进制，例如：1010（10）其表示的是1010，1010（2）表示的是10
2.二进制加法
二进制加法采用的是从低到高的位次相加，当相加的和为2时，则向高位进位
例如：
3.二进制的减法
二进制减法采用从低到高的位次依次相减，当遇到0减1的情况，则向高位借位
例如：
2.位运算简介
3.位运算概括
1.布尔运算
| 运算符表示 | 含义 | 示例 |
| & | 位与 | x&y |
| | | 位或 | x|y |
| ^ | 异或 | x^y |
| ~ | 按位取反 | x~y |
1.位与（一假便假）
| 左操作数 | 右操作数 | 结果 |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
public static void main(String[] args) {
int a=110;
int b=0b110;
System.out.println(a);//110
System.out.println(b);//6
}- 以0b作为前缀的表示它是一个二进制数
位与运算符的应用：
1.奇偶性判定
一般我们判断奇偶数的时候，都是取模进行判断
int a=15;
if(a%2==0){
System.out.println("我是一个偶数");
}else{
System.out.println("我是一个奇数");
}我们学了位运算之后就可以这样写
int a=15;
if((a&1)==0){
System.out.println("我是一个偶数");
}else{
System.out.println("我是一个奇数");
}这是因为在二进制中奇数的最后一位是1，偶数的最后一位是0，故&可以求得该数奇偶性
2.取末5位
给定一个数，求它的二进制表示的末5位，以十进制输出即可
可以给 给定的数位与个0b11111,取到末5位的值
x&0b111113.消除末尾5位
给定一个数32位的整数，要求消除它的末5位
（11111111111111111111111111100000）（2）
代码这么写确实是复杂，看到都有点头晕，一般我们把它转成16进制，每4个二进制可以转换为一个16进制的数，所以得到的16位进制的数为0xffffffe0
x&0xffffffe0
//f代表的是4个1 e代表的是3个1，1个0 0代表的是4个04.消除末尾连续1
给出一个整数，现要求将这个整数转换成二进制数，将末尾连续的1都变为0，输出改变后的数字
- 原二进制表示形式：
- 如果我们给这个原二进制数字上末尾加个1：
- 然后将这两个数进行位与运算：
5.2的幂判定
怎么样才能判断一个正数是不是2的幂次？
- 如果一个数是2的幂次，它的二进制表示必然是：
- 我们将它减1，即2的k次减1的二进制表示如下：
- 于是这两个数位与的结果也为0，于是我们知道一个数x是2的幂次，那么x&(x-1)必然为0
-
(x&(x-1))==0
2.位或（一真便真）
| 左操作数 | 右操作数 | 结果 |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
1.位或运算符的应用
1.设置标记位
给定一个数，判断它二进制低位的第5位，如果是0，则将它置为1
x|0b100002.置空标记位
- 首先，强行将低位的第5位换成1
- 然后，强行将低位的第5位去掉
int a=0b10000
((x|a)-a)注意：直接减是不行的，因为我们要保证那一位为1，不然会造成借位，影响结果
3.低位连续零变一
给定一个整数x,将它低位连续的0都变为1
- 假设这个整数低位有连续k个零，二进制表示为：
- 减一操作得：
- 两数进行位或操作：
x|(x-1)4.低位首零变一
3.异或（相同为0，不同为1）
| 左操作数 | 右操作数 | 结果 |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
1.异或运算符的应用
1.标记位取反
给定一个数，将它的低位数起的第4位进行取反，0变1 1变0
x^0b100002.变量交换
给定两个数，用异或运算交换它们的值
int a=5;
int b=15;
a=a^b;
b=a^b;
a=a^b;
System.out.println(a);//15
System.out.println(b);//53.出现奇数次的数
输入n个数，其中只有一个数出现了奇数次，其他所有数都出现了偶数次，求这个出现了奇数次的数
根据异或的性质，两个一样的数异或结果为0，也就是所有出现偶数次的数异或为0，那么把n个数都异或一下，得到的数一定是那个出现奇数的数
int[] num={2,2,3,4,4,5,5};
int ans=0;
for(int n:num){
ans^=n;
}
System.out.println(ans);4.丢失的数
如果两个相同的数异或为零，那么这个数中，处了丢失的数之外，其余的数都可以找到两两结对异或得零，最后的结果就是0和丢失的数异或，因为0和任何数异或都是这个数的本身，自然地到了丢失的数
5.简单加密
基于两个数异或为0，任何数和零异或为其本身这两个特点，异或还可以用来做简单的加密，将明文异或上一个固定的数变成密文后，可以通过继续异或上这个数，再将密文转成明文
4.按位取反
0变1 1变0
2.移位位运算
| 运算符表示 | 含义 | 示例 |
| << | 左移 | x<<y |
| >> | 右移 | x>>y |
1.左移：
其中x<<y代表将二进制的x的末尾添加y个0，向左移动了y位 1011<<3 =1011000
2.右移：
其中x>>y代表将二进制的x的右边截掉y个0，向右移动了y位 101111>>3 =101
4.将一个hash表压缩成一个数字(只是适用于元素较少的hash表)
空集 -------0
只含有第i个元素的集合{i}---------1<<i
含有全部n个元素的集合{0，1，...，n-1}-------(1<<n)-1
判断第i个元素是否属于集合S-------------if(S>>1&1)
向集合S中加入第i个元素--------------S|1<<i;
从集合S中取出第i个元素--------------S&~(1<<i) S^(1<<i)
集合S和T的并集------------S|T
集合S和T的交集------------S&Tleetcode题单：
位1的个数
public int hammingWeight(int n) {
int count=0;
for(int i=0;i<32;i++){
if((n&1)==1){
count++;
}
n>>=1;
}
return count;
}只出现一次的数字
public int singleNumber(int[] nums) {
if(nums.length==0){
return 0;
}
Arrays.sort(nums);
Stack stack=new Stack();
for (int i = 0; i<=nums.length-1; i++) {
stack.push(nums[i]);
if(stack.peek().equals(nums[nums.length-1])){
return (int)stack.peek();
}
if(stack.peek().equals(nums[i+1])){
stack.pop();
i++;
}else{
return (int)stack.peek();
}
}
return (int)stack.peek();
}
