算法 - 位运算

[Petelin]

算法 - 位运算

10进制数字和2进制数字

数字只有两种:

奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。

举例：

0 = 0 1 = 1
2 = 10 3 = 11

偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。

举例：

2 = 10 4 = 100 8 = 1000
3 = 11 6 = 110 12 = 1100

如果我们想求一个数字里面1的个数那么, 有这样的状态转移方程

P(x)=P(x / 2)+(x mod 2)

或者

P(x) = P(x-1) + 1 如果x是奇数

P(x) = P(x / 2) 如果x是偶数

高级位操作

get 最后一位(op=3)

y = x & (-x); // 1110 -> 0010

pop/删除 最后一个1 (op=2)

y = x & (x - 1); // 1110 -> 1100

get 最高位

最高位没有办法像最低位一样求出来, 只能先求出来高位

每次pop最后一位, 记录最后一次不为0的数字(即只有一个1的数字)

// 1110 -> 1000
func getHigh2(num int) int {
	ans := 0
	for num > 0 {
		ans = num
		num = num & (num - 1)
	}
	return ans
}

高位低位都能用的二分查找, 选取的解空间很精髓 [0, N]

func getHigh(num int) int {
	left := 0
	right := int(unsafe.Sizeof(int(0)) * 8)
	for left < right {
		mid := left + (right-left+1)/2
		if num < (1 << uint64(mid)) {
			right = mid - 1
		} else {
			left = mid
		}
	}
	return left
}

真值表 -> 逻辑表达式

通过真值表就可以得到一个逻辑表达式

https://leetcode-cn.com/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-shu-zi-dian-lu-she/

通过位操作进行大小写转换

因为'a' 和 'A' 之间差了 32 个数, 所以用

x ^ 32

就完成了大小写转换

INT/UNSIGN INT 值的范围. 补码

// uint
const MaxUint = ^uint(0)
const MinUint = 0

// int: max
const MaxInt = int(MaxUint >> 1)
const MaxInt2 int = 1<<63 - 1
const MaxInt3 = int(^(uint64(1) << 63))

// int: min
const MinInt = ^MaxInt
const MinInt2 = -MaxInt - 1
const MinInt3 = -1 << 63
const MinInt4 = -(1 << 63)

[Petelin]

this code show us that const value is pre-calculated. since `MaxInt+1 cannot be const int`.  `MaxInt + 1` 是一个const值，只是不能是const int

const MaxInt = int(^uint64(0) >> 1)

func main() {
	var a int = MaxInt
	fmt.Println(a + 1)

	// panic ./test_main.go:86:21: constant 9223372036854775808 overflows int
	// fmt.Println(MaxInt + 1)
}

[Petelin]

官方库做法
// int: max
const MaxInt2 int = 1<<63 - 1 【0111111111111111111111111111..................】

// int: min
const MinInt3 = -1 << 63 【100000000000000.................】