在实习过程中使用了位操作去操作bitmap, 学习一下位操作的相关知识, 提高位运算的敏感程度
异或
异或的意思就是无进位相加, 就是没有进位的相加. 满足交换律与结合律
例如
A : 01101110
B : 10011101
A^B: 11110011
所以
- 由无进位相加的理解可以得到,
0^A = A,A^A = 0 - 由交互律可以得到
A^B=C -> B^C=A -> A^C=B- 所以: 整体异或的结果是A, 整体中的部分的结果是B, 那么剩余部分的异或是A^B
所以可以有一个有意思的问题:
如果有a个黑球, b个白球, 每次从袋子里拿两个球, 如果两个黑色/两个白色, 那么放进去一个白球, 如果一黑一白, 那么放进去一个黑球, 那么最终一定剩下了一个球, 那么这个球是黑球的概率是?
如果a是偶数, 那么就是0, 如果是奇数, 那么就是100%
这个问题的理解就是那个整体与部分的关系, 白球就是0, 黑球就是1
有意思的Bit运算代码
交换两个数
a = a^b
b = a^b
a = a^b
找到缺失的那个值
func getMisNum(arr []int) int {
allEor, hasEor := 0, 0
for k, v := range arr {
allEor ^= k
hasEor ^= v
}
allEor ^= len(arr)
return allEor ^ hasEor
}
func main() {
println(getMisNum([]int{0, 1, 2, 4, 5, 6}))
}
找到唯一一个出现奇数次的数
func getOddNum(arr []int) int {
ans := 0
for _, v := range arr {
ans ^= v
}
return ans
}
func main() {
println(getOddNum([]int{1, 2, 3, 4, 5, 1, 3, 4, 5, 1, 1}))
}
找到两个出现奇数次的数
补充: Brian Kernighan 算法 取最右侧的1(eg, 10101010 -> 00000010, 10111000-> 00001000)
A : 10111000
~A : 01000111
~A+1 : 01001000 其实这个就是它的相反数 -n
A&(~A+1): 00001000
A&(-A) : 00001000 其实与上面那个是一样的
func getTwoOddNum(arr []int) (int, int) {
// 如果这两个数是a, b
// eor1 就是 a ^ b
eor1, eor2 := 0, 0
for _, v := range arr {
eor1 ^= v
}
// 找到最右侧的那个1在哪里
// a 与 b 肯定在这一位不同, 否则就不是1了嘛
// 根据最右侧的那一位是不是1, 可以分成两波数字, a 在一波, b在另一波
// 任意将 等于0 或者 不等于零 的那一波异或起来
// 得到的就是 a or b
right_ont := eor1 & (-eor1)
for _, v := range arr {
// 这里也可以是 != 0
if (v & right_ont) == 0 {
eor2 ^= v
}
}
return eor2, eor1 ^ eor2
}
func main() {
println(getTwoOddNum([]int{1, 2, 3, 3, 4, 4, 5, 5, 6, 6}))
}
返回出现次数小于k次的数
func findLowK(arr []int, k int) int {
count, ans := make([]int, 32), 0
for _, v := range arr {
for i := 0; i < 32; i++ {
count[i] += (v >> i) & 1
}
}
// 看看那一位不符合要求, 那么ans一定含有这一位
for i := 0; i < 32; i++ {
if count[i]%k != 0 {
ans |= 1 << i
}
}
return ans
}
func main() {
println(findLowK([]int{1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5}, 5))
}
判断一个数是不是2的倍数
func judgePowerOfTwo(n int) bool {
// 2的倍数就是只有一个1
// 就是使用brian kernighan算法, 提取出来以后判断
// 如果不相等, 那就不止一个1, 就不是2的倍数
// 如果相等, 就只有一个1, 那么就是2的倍数
return n > 0 && n == n&(-n)
}
func main() {
println(judgePowerOfTwo(406))
}
求大于n的最小的2的幂
func near2power(n int) int {
// 小于0的最接近的都是1
if n < 0 {
return 1
}
/*
--后,return再+1的目的:防止这个数就是2的幂
*/
n--
/*
这一堆的目的就是把最高位后面的都刷成1
n: 0000 1000 1100 1010 0000 0000 0000 0001
n--: 0000 1000 1100 1010 0000 0000 0000 0000
*/
// n: 0000 1000 1100 1010 0000 0000 0000 0001
// n--: 0000 1000 1100 1010 0000 0000 0000 0000
n |= n >> 1 // 0000 1100 1100 1010 0000 0000 0000 0000
n |= n >> 2 // 0000 1111 1100 1010 0000 0000 0000 0000
n |= n >> 4 // 0000 1111 1111 1010 0000 0000 0000 0000
n |= n >> 8 // 0000 1111 1111 1111 1111 0000 0000 0000
n |= n >> 16 // 0000 1111 1111 1111 1111 1111 1111 1111
return n + 1 // 0001 1111 1111 1111 1111 1111 1111 1111
}
求正整数[left, right]内所有值&的结果
/*
& 的结果就是 某一位 只要包含一个0, 这一位的结果就永远是0了
例子:
l: 0000 0000 0000 0001
r: 0100 0110 1000 0000
分析:
对于r来说
如果r == l的话, 那么结果就是 r & r = r
如果r != l => r-1一定在这个区间里 => 一定会有操作 r & r-1
r: 0100 0110 1000 0000
& r-1: 0100 0110 0111 1111
ans: 0100 0110 0000 0000
所以r最右边那个1(自己包含在内), 后面的结果都是零, 那么最终结果一定都是0了
那么可以不考虑这一堆0了
那么就下面就考虑去掉最右边1的那个r了
*/
func rangeBitwiseAnd(left, right int){
for left < right {
// brian kernighan 求出最右边的1, 然后减掉
right -= right & -right
}
return right
}
逆序一个二进位
/*
n: 0000 0000 0000 0000 0010 0000 1001 0101
ans: 1010 1001 0000 0100 0000 0000 0000 0000
1. 以1bit位单位 每2bit之间交换
n: 00 00 00 00 00 00 00 00 00 10 00 00 10 01 01 01
-> 00 00 00 00 00 00 00 00 00 01 00 00 01 10 10 10
2. 以2bit为单位 每4bit之间交换
-> 0000 0000 0000 0000 0001 0000 0110 1010
-> 0000 0000 0000 0000 0100 0000 1001 1010
3. 以4bit为单位 每8bit之间交换
-> 00000000 00000000 01000000 10011010
-> 00000000 00000000 00000100 10101001
4. 以8bit为单位 每16bit之间交换
-> 0000000000000000 0000010010101001
-> 0000000000000000 1010100100000100
5. 以16bit为单位 每32bit之间交换
-> 0000000000000000 1010100100000100
-> 1010100100000100 0000000000000000
*/
func reverseBits(n int) int {
// 0xaaaaaaaa = 0b10 10 10 10 10 ....
// 0x55555555 = 0b01 01 01 01 01 ....
n = ((n&0xaaaaaaaa)>>1 | (n&0x55555555)<<1)
// 0xcccccccc = 0b1100 1100 ....
// 0x33333333 = 0b0011 0011 ....
n = ((n&0xcccccccc)>>2 | (n&0x33333333)<<2)
// 0xf0f0f0f0 = 0b11110000 11110000
// 0x0f0f0f0f = 0b00001111 00001111
n = ((n&0xf0f0f0f0)>>4 | (n&0x0f0f0f0f)<<4)
// ....
n = ((n&0xff00ff00)>>8 | (n&0x00ff00ff)<<8)
n = (n >> 16) | (n << 16)
return n
}
func main() {
fmt.Printf("%b", reverseBits(0b10000010010101))
}