二进制

常见二进制操作

基本操作

a=0^a=a^0
0=a^a
由上面两个推导出:a=a^b^b

交换两个数

a=a^b
b=a^b
a=a^b

移除最后一个 1

a=n&(n-1)

获取最后一个 1

diff=(n&(n-1))^n

常见题目

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
1
func singleNumber(nums []int) int {
2
// 10 ^10 == 00
3
// 两个数异或就变成0
4
result:=0
5
for i:=0;i<len(nums);i++{
6
result=result^nums[i]
7
}
8
return result
9
}
Copied!
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
1
func singleNumber(nums []int) int {
2
// 统计每位1的个数
3
var result int
4
for i := 0; i < 64; i++ {
5
sum := 0
6
for j := 0; j < len(nums); j++ {
7
// 统计1的个数
8
sum += (nums[j] >> i) & 1
9
}
10
// 还原位00^10=10 或者用| 也可以
11
result ^= (sum % 3) << i
12
}
13
return result
14
}
Copied!
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
1
func singleNumber(nums []int) []int {
2
// a=a^b
3
// b=a^b
4
// a=a^b
5
// 关键点怎么把a^b分成两部分,方案:可以通过diff最后一个1区分
6
7
diff:=0
8
for i:=0;i<len(nums);i++{
9
diff^=nums[i]
10
}
11
result:=[]int{diff,diff}
12
// 去掉末尾的1后异或diff就得到最后一个1的位置
13
diff=(diff&(diff-1))^diff
14
for i:=0;i<len(nums);i++{
15
if diff&nums[i]==0{
16
result[0]^=nums[i]
17
}else{
18
result[1]^=nums[i]
19
}
20
}
21
return result
22
}
Copied!
编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
1
func hammingWeight(num uint32) int {
2
res:=0
3
for num!=0{
4
num=num&(num-1)
5
res++
6
}
7
return res
8
}
Copied!
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。
1
func countBits(num int) []int {
2
res:=make([]int,num+1)
3
4
for i:=0;i<=num;i++{
5
res[i]=count1(i)
6
}
7
return res
8
}
9
func count1(n int)(res int){
10
for n!=0{
11
n=n&(n-1)
12
res++
13
}
14
return
15
}
Copied!
另外一种动态规划解法
1
func countBits(num int) []int {
2
res:=make([]int,num+1)
3
for i:=1;i<=num;i++{
4
// 上一个缺1的元素+1即可
5
res[i]=res[i&(i-1)]+1
6
}
7
return res
8
}
Copied!
颠倒给定的 32 位无符号整数的二进制位。
思路:依次颠倒即可
1
func reverseBits(num uint32) uint32 {
2
var res uint32
3
var pow int=31
4
for num!=0{
5
// 把最后一位取出来,左移之后累加到结果中
6
res+=(num&1)<<pow
7
num>>=1
8
pow--
9
}
10
return res
11
}
Copied!
给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。
1
func rangeBitwiseAnd(m int, n int) int {
2
// m 5 1 0 1
3
// 6 1 1 0
4
// n 7 1 1 1
5
// 把可能包含0的全部右移变成
6
// m 5 1 0 0
7
// 6 1 0 0
8
// n 7 1 0 0
9
// 所以最后结果就是m<<count
10
var count int
11
for m!=n{
12
m>>=1
13
n>>=1
14
count++
15
}
16
return m<<count
17
}
Copied!

练习

最近更新 1yr ago