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&0b11111
3.消除末尾5位
给定一个数32位的整数,要求消除它的末5位
(11111111111111111111111111100000)(2)
代码这么写确实是复杂,看到都有点头晕,一般我们把它转成16进制,每4个二进制可以转换为一个16进制的数,所以得到的16位进制的数为0xffffffe0
x&0xffffffe0
//f代表的是4个1 e代表的是3个1,1个0 0代表的是4个0
4.消除末尾连续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|0b10000
2.置空标记位
- 首先,强行将低位的第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^0b10000
2.变量交换
给定两个数,用异或运算交换它们的值
int a=5;
int b=15;
a=a^b;
b=a^b;
a=a^b;
System.out.println(a);//15
System.out.println(b);//5
3.出现奇数次的数
输入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&T
leetcode题单:
位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();
}