2025年leetcode位运算

科技前沿 • 2025-01-10 08:41 • 阅读 73

大家好，我是讯享网，很高兴认识大家。

1.位运算
&与
|或
^异或
～取反
<<左移
">>"有符号右移
">>>"无符号右移

2.有符号整数和无符号整数
0000 1010 正数
1000 1010 负数
第一位为符号位，正数的符号位为0，负数的符号位为1

3.原码、反码、补码

原码
10: 00000000 00000000 00000000 00001010
-10: 00000000 00000000 00001010

反码
符号位不变，其余为取反
10:0
-10:

补码
正数的补码等于原码负数的补码等于反码+1
10:00000000 00000000 00000000 00001010
-10:

4.为什么使用补码
（1）统一数字0的表示
+0: 00000000 00000000 00000000 00000000
-0:
原码 00000000 00000000 00000000
反码
补码 00000000 00000000 00000000 00000000

0000000 00000000 00000110
00000000 00000000 00000000 00000101
=
00000000 00000000 00001011
=-11 结果是错的
所以要用补码
（-6的补码）
+
00000000 0000000 0000000 00000101（5的补码）

(-1的补码）

把结果还原成原码：
先减掉1
再取反 00000000 00000000 00000001（-1的原码）

5.有符号整数二进制规律
4位
0000 0
0001 1
0010 2
…
0111 7
1000（以补码的方式存在） -8
1001 -7
1010 -6
1011 -5
1100 -4
1101 -3
1110 -2
1111 -1
-2(n-1) ~ 2(n-1)-1

所以 int的范围是
-231 ~ 231-1

6.按位取反
9的原码 1001
9的补码 01001
取反 10110（补码）
还原成原码（-1，取反码） 11010
得到结果：～9 = -10

7.左移<< 右移>> 无符号右移>>>
4: 00000000 0000000 00000000 00000100
4<<2:0000000 00000000 00000000 00010000
左移低位补0
-4(补码）:
-4<<2:
转成原码（-1，取反码） 00000000 00000000 00010000 = -16

左移和符号没有关系，不会改变正负号。

15: 0000000 00000000 0000000 00001111
15>>2: 00000000 00000000 00000000 00000011
15>>>2: 00000000 00000000 00000000 00000011

讯享网

-15: （补码）
-15>>2: （补码）
减1取反后得 00000000 00000000 00000100
-15>>>2: 00
=

8.位运算技巧
（1）拿到二进制的低16位： n&0xFFFF
n : 00001010 00010000 00001010
&
00000000 00000000
00000000 00000000 00001010

（2）对二进制的高16位取反：～(n^0xFFFF) 0xFFFF–>mask掩码
先对低16位取反，再对整个取反(跟1异或等于取反）
n: 00001010 00010000 00001010
^
00000000 00000000
= 00001010 00010000 00001101
~
00001010

测试第i+1位是否为1:(n&1<<i)!=0
选择掩码1，与数字取&，得到的结果即第1位的结果
如果要测试第二位，则将1<<1
如果要测试第三位，则将1<<2

去掉最后一位1： n&(n-1)
n. : 00001010 00010000 00001010
&
n-1: 00001010 00010000 00001001
=00001010 00010000 00001000

获取最后一位1:
n&-n
n: 00001010 00010000 00001010
&
-n(补码）: 00001101
= 00000000 00000000 00000000 00000010

A的位减去B的位 A&~B
A: 00001011 00000000
B: 00000001 00
~B: 00 0
&
=00001010 00000000 0

^的用法技巧
a^0 = a
a^a = 0
a^ (b^ c) = a ^ (c^b) 交换率

利用技巧：判断第i位是否为1

class Solution: def hammingWeight(self, n: int) -> int: res = 0 for i in range(1,33): if ((n&1<<(i-1)) !=0): res += 1 return res

讯享网

右移n位，每次右移时，判断第1位是否为1

讯享网class Solution: def hammingWeight(self, n: int) -> int: res = 0 for i in range(1,33): if ((n>>(i-1))&1!=0): res += 1 return res

每次移除掉最后一个1，直到n为0

class Solution: def hammingWeight(self, n: int) -> int: res = 0 while n != 0: n = n & (n-1) res+=1 return res

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

对异或后的结果统计有多少1.

讯享网class Solution: def hammingDistance(self, x: int, y: int) -> int: diff = x^y res = 0 while diff != 0: diff = diff&(diff-1) res += 1 return res

在这里插入图片描述
解法1:暴力解法

class Solution: def totalHammingDistance(self, nums: List

2025年leetcode位运算

0000000 00000000 00000110 00000000 00000000 00000000 00000101 = 00000000 00000000 00001011 =-11 结果是错的 所以要用补码 （-6的补码） + 00000000 0000000 0000000 00000101（5的补码）

相关推荐

0000000 00000000 00000110
00000000 00000000 00000000 00000101
=
00000000 00000000 00001011
=-11 结果是错的
所以要用补码
（-6的补码）
+
00000000 0000000 0000000 00000101（5的补码）