前段时间刷到了力扣关于位运算的题,这里浅浅记录一下!
1. 逻辑位运算
1.1 与 &
&:按位与进行二进制计算,规则是同为1则为1,不同为0,具体如下:
0&0=0, 0&1=0, 1&0=0, 1&1=1
要对所有的条件都进行判断操作,如a = 1 & 2,结果a = 0,也相当于求每位的进位数,如9 & 1 = 1。
注意:
还有一种相似的与逻辑运算符, &&
,称为逻辑与,也称短路与,只要第一个条件不满足,后面条件就不再判断;如a = 1 > 0&& 2 < 1,结果a = false。
1.2 或 |
|:按位或二进制计算,规则是同为0则为0,否则为1,具体如下:
0&0=0, 0&1=1, 1&1=1, 1&1=1
要对所有的条件都进行判断,如a = 3|5,结果a = 7。
注意:
还有一种相似的或逻辑运算符 ||
:称为逻辑或,也称短路或,仅需要其中一个条件满足即可,其它条件就不再判断,如 a = 2 > 0 || 3 > 1,结果a = true。
1.3 非
****:按位进行取反进行二进制计算,规则是1取反为0,0取反为1,如37 = -38,具体计算如下:
在Java中,int 占四个字节,一个字节占8bit位,即32位,32bit.
37转为二进制是:100101.
计算机保存的都是补码,37是正数,他的原码,反码,补码都是一样的;
37在计算机中的补码:
00000000 00000000 00000000 00100101
~37的计算:
A.求37在计算中补码的相反码(不是反码),这里还是补码只是相反的补码
11111111 11111111 11111111 11011010
B:将相反的补码,转换为原码,由于相反码的第一个位是1,这个数是负数,负数的补码转反码 减一(-1)
11111111 11111111 11111111 11011010 -1
=
11111111 11111111 11111111 11011001
反码转原码:符号位不变,其他数相反
10000000 00000000 00000000 00100110
二进制100110十进制38
符号位不变-38
注意:
还有一种相似的运算符 !:称为逻辑非,对当前结果取反即可,具体如下:
!1 = 0, !0 = 1
如 !false
= true
, !true
= false
。
1.4 异或
符号为^
, 规则是相同为0,不同为1,具体如下:
1^0 = 1 , 1^1 = 0 , 0^1 = 1 , 0^0 = 0
相当于无进位的求和,不考虑进位,如 1 ^ 2 = 3,即001 ^ 010 = 011;19 ^ 1 = 10。
2. 移位运算符
2.1左移运算符<<
- 运算规则是:按二进制形式把所有的数字向左移动对应的位数,高位移出(舍弃),低位的空位补零。
- 若移动的位数超过了该类型的最大位数,那么编译器会对移动的位数取模。如对int型移动33位,实际上只移动了1位。
- 语法格式:需要移位的数字number << 移位的次数,如5 << 1,相当于5乘以2的1次幂,结果为10。
- 数学意义:在数字没有溢出的前提下,对于正数和负数,左移一位都相当于乘以2的1次方,左移n位就相当于乘以2的n次方。
2.2 右移运算符>>
- 运算规则是:按二进制形式把所有的数字向右移动对应位移位数,低位移出(舍弃),高位的空位补符号位,即正数补零,负数补1。
- 若移动的位数超过了该类型的最大位数,那么编译器会对移动的位数取模。如对int型移动33位,实际上只移动了1位。
- 语法格式:需要移位的数字number >> 移位的次数,如4 >> 1,相当于4乘以2的1次幂,结果为2。
- 数学意义:右移一位相当于除2,右移n位相当于除以2的n次方。
2.3 无符号右移 >>>
- 运算规则是:按二进制形式把所有的数字向右移动对应位移位数,低位移出(舍弃),高位的空位补符号位0,忽略了符号位扩展,即不管是正数还是负数都补0。
- 语法格式:需要移位的数字number >>> 移位的次数。
- 只是对32位和64位的值有意义。
3. 小知识
3.1 判断某二进制数n最低(右)位1或者0
- 若 n & 1 = 0,则 n二进制数n最右一位 为 0;
- 若 n & 1 = 1,则 n二进制数n最右一位 为 1;
可用于题目:判断所给数字转换为二进制数中1的个数
3.2 二进制数n最低(右)位1变为0
- n&(n−1): 二进制数n最右边为1,n-1最右边则为0;
- n>>>1 :直接对二进制数n进行无符号右移1位
3.3 不使用运算符+求两数和
- 先用异或运算进行无进位求和,即 a^b;
- 再用与运算进行处理每次进位并左移一位,即(a &b) << 1;
- 两者用异或运算求和,即(a^b) ^ ((a &b) << 1);
- 重复上述过程,直到进位为0即可;