golang 位运算

go 评论

二进制表示

从现代计算机中所有的数据二进制的形式存储在设备中。即 0、1 两种状态。
例如 用8位存储
1
2
3
4
5
0: 00000000    
1: 00000001  2^0
2: 00000010  2^1
3: 00000011  2^1 + 2^0
4: 00000100  2^2
可以使用如下公式 f(a) = 2^(x-1) x为位数

位运算

从现代计算机中所有的数据二进制的形式存储在设备中。即 0、1 两种状态，计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，即将符号位共同参与运算的运算。
1
2
3
a := 3
b := 6
c := 9
计算两个数的和，因为在计算机中都是以二进制来进行运算，所以上面我们所给的 int 变量会在机器内部先转换为二进制在进行相加
1
2
3
4
3:   0 0 0 0 0 0 1 1
7:   0 0 0 0 0 1 1 1
————————————————————
10:  0 0 0 0 1 0 1 0
可以如下表示
1
2
3
3 = 2^1 + 2^0
7 = 2^2 + 2^1 + 2^0
10 = 2^3 + 2^1

位运算符

位运算符对整数在内存中的二进制位进行操作
运算符 描述
& 参与运算的两数各对应的二进位相与。 （两位均为1才为1）
^ 参与运算的两数各对应的二进位相异或，当两对应的二进位相异时，结果为1。 （两位不一样则为1）
<< 左移n位就是乘以2的n次方。 “a<<b”是把a的各二进位全部左移b位，高位丢弃，低位补0。
>> 右移n位就是除以2的n次方。 “a>>b”是把a的各二进位全部右移b位。
&^ 位与非，AND NOT
与运算 &
参与运算的两数各对应的二进位相与。就是2为都为1 则结果为1，有一位为0，结果都为0
运算符为**&**
1
2
3
4
a := 1     # 00000001
b := 3     # 00000011
c := a & b # 00000001

参与运算的两数各对应的二进位相或。 （两位有一个为1就为1）
运算符为 |
1
2
3
4
a := 1     # 00000001
b := 4     # 00000100
c := a | b # 00000101

异或 ^
参与运算的两数各对应的二进位相异或，也就是当两对应的二进位相异时，结果为1
运算符为^
1
2
3
4
a := 1      # 00000001
b := 5      # 00000101
c := a ^ b  # 00000100

<< 和 >> 运算符
1
2
3
a << n; 将 a 中的所有位向左偏移 n 次
a >> n; 将 a 中的所有位向右偏移 n 次

1
2
3
4
5
6
7
8
9
10
11
12
var a int8 = 3
fmt.Printf("%08b\n", a)
fmt.Printf("%08b\n", a<<1)
fmt.Printf("%08b\n", a<<2)
fmt.Printf("%08b\n", a<<3)
fmt.Printf("%08b\n", a>>1)
# print
#00000011
#00000110
#00001100
#00011000
#00000001
&^ 运算符
&^ 运算符叫做 AND NOT。它是一个 使用 AND 后，再使用 NOT 操作的简写。该操作符定义如下：
a 与b的负数相与
1
2
3
4
5
Given operands a,b
AND_NOT(a, b) = AND(a, NOT(b))
// 给定两个操作数 a,b		
// 当 a=NOT(b)=1 时，操作 AND_NOT(a, b) 返回 1。
// 否则返回 0。
它有一个有意思的特性：如果第二个操作符返回 1。那么该位将会被清 0
1
2
AND_NOT(a, 1) = 0; clears a
AND_NOT(a, 0) = a;

相关应用

测试第 n 位是不是指定的值

1 << n位，然后&运算

1
2
3
4
5
6
7
var a int8 = 12
fmt.Printf("%08b\n", a)

n := 3
if s := a & (1 << n); s != 0 {
  fmt.Printf("a的%d位为1 \n", n)
}

计算一个数 *4

数左移2位
1
2
3
var a int8 = 12
fmt.Printf("%08b %d \n", a<<2, a<<2)

去除后4位

使用 AND NOT (&^)操作符来清掉 a 的后 4 位
1
2
3
4
5
6
7
8
ar a byte = 0x1A
fmt.Printf("%08b\n", a)

a = a &^ 0x0F
fmt.Printf("%08b\n", a)

#00011010
#00010000
或者 注意 0x0F与0xF0区别

补数

求数字的补数https://leetcode.cn/problems/number-complement/
1
2
3
4
5
6
7
8
9
10
476. 数字的补数
对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。
给你一个整数 num ，输出它的补数。

示例 1：
输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
题解 这里用到异或^
1
2
3
4
5
6
7
8
9
10
11
12
func findComplement(num int) int {
	highBit := 0
	for i := 0; i < 32; i++ {
		if num < 1<<i {
			break
		}
		highBit = i
	}
	mask := 1<<(highBit+1) - 1 // 最高位
	ans := num ^ mask
	return ans
}

汉明距离

求461. 汉明距离 https://leetcode.cn/problems/hamming-distance/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
461. 汉明距离
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：
输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
上面的箭头指出了对应二进制位不同的位置。

示例 2：
输入：x = 3, y = 1
输出：1
题解，使用异或^ 然后计算1的个数
1
2
3
4
5
6
7
8
func hammingDistance(x int, y int) int {
   ans := 0
   // 异或 然后右移，判断最后一位是否是1
   for s := x ^ y; s > 0; s >>= 1 {
      ans += s & 1 // 判断最后一位是否为1
   }
   return ans
}

CSS一只热爱生活的程序猿

个人简介。