python 位运算 笔记

起因， 目的:

位运算，令我头疼的地方。算法题里面也是经常见到。

位运算。

1. 按位或，OR, | , 只要有一个为1， 结果就是1，否则为0
2. 按位异或，XOR, ^, 2个数不同，结果为1， 否则为0，
   • 可以判断2个数的奇偶性是否相同。
   • 如果2个数的奇偶性相同，结果0
   • 如果2个数的奇偶性不同，结果1
3. 按位与， AND, &, 都为1， 结果为1
4. 按位取反，NOT, ~, 把1变为0， 把0变为1

技巧

1. n & 1, 判断奇偶性.

   • 如果n是奇数，则结果为 1
   • 如果n是偶数，则结果为 0

2. n >> 1, 右移一位，

   • 相当于除以2之后的整数部分， 即 n//2. 如n=10，则n>>1=5.

3. n & (n - 1)，把 n 的二进制中，最后一个出现的 1 改写成 0。

4. 移位运算，能大大加速2的n次方运算。

   • 3 << 5 = 3 * 2 ** 5 = 96

异或 运算的基础知识:

概念理解:

1. 异或，英文为 exclusive OR，缩写成xor, python3: a^b, 3^5
2. 异或, 满足加法结合律和交换律
3. 异或, 也叫半加运算， 相当于不带进位的二进制加法
4. 不是这个就是那个。“我明天要么去北京，要么去上海”
5. 异或的可逆运算, 本质上还是一个结合律
   49 ^ 213 ^ 213 -> 49 ^ (213 ^ 213) -> 49 ^ 0 -> 49

定律:

1. 如果有 a^b=c， 必有 a^c=b, 也必然有 b^c=a
2. if a !=b: a^b=1, if a=b: a^b = 0
3. a ^ a = 0 a ^ 0 = a # 任何数与 0 异或，都等于它自身。
4. a^bc = b^ca = c^ba, 这里的交换律是解题的关键。
5. 一句话总结:
   1. 7⁸9 = 8⁷9 = 9⁷8 = 6,
   2. 其中， 7^8 = 15， 15^9=6
   3. 这个 15 就是中间的一个 中转站。

位运算

1. 位运算的一个好处是可以节省内存，也许还有其他好处。需要再查查看。
2. 60 << 2 = 240
   左移动位运算 运算数的各二进位全部左移若干位，由"<<"右边的数指定移动的位数，
   高位丢弃，低位补0。

---

老哥留步，支持一下。