python 位运算 笔记
起因， 目的:
位运算，令我头疼的地方。算法题里面也是经常见到。
位运算。
- 按位或，OR, | , 只要有一个为1， 结果就是1，否则为0
- 按位异或，XOR, ^, 2个数不同，结果为1， 否则为0，
- 可以判断2个数的奇偶性是否相同。
- 如果2个数的奇偶性相同，结果0
- 如果2个数的奇偶性不同，结果1
- 按位与， AND, &, 都为1， 结果为1
- 按位取反，NOT, ~, 把1变为0， 把0变为1
技巧
-
n & 1, 判断奇偶性.
- 如果n是奇数，则结果为 1
- 如果n是偶数，则结果为 0
-
n >> 1, 右移一位，
- 相当于除以2之后的整数部分， 即 n//2. 如n=10，则n>>1=5.
-
n & (n - 1)，把 n 的二进制中，最后一个出现的 1 改写成 0。
-
移位运算，能大大加速2的n次方运算。
- 3 << 5 = 3 * 2 ** 5 = 96
异或 运算的基础知识:
概念理解:
- 异或，英文为 exclusive OR，缩写成xor, python3: a^b, 3^5
- 异或, 满足加法结合律和交换律
- 异或, 也叫半加运算， 相当于不带进位的二进制加法
- 不是这个就是那个。“我明天要么去北京，要么去上海”
- 异或的可逆运算, 本质上还是一个结合律
49 ^ 213 ^ 213 -> 49 ^ (213 ^ 213) -> 49 ^ 0 -> 49
定律:
- 如果有 a^b=c， 必有 a^c=b, 也必然有 b^c=a
- if a !=b: a^b=1, if a=b: a^b = 0
- a ^ a = 0 a ^ 0 = a # 任何数与 0 异或，都等于它自身。
- abc = bca = cba, 这里的交换律是解题的关键。
- 一句话总结:
- 789 = 879 = 978 = 6,
- 其中， 7^8 = 15， 15^9=6
- 这个 15 就是中间的一个 中转站。
位运算
- 位运算的一个好处是可以节省内存，也许还有其他好处。需要再查查看。
- 60 << 2 = 240
左移动位运算 运算数的各二进位全部左移若干位，由"<<"右边的数指定移动的位数，
高位丢弃，低位补0。
老哥留步，支持一下。
