算法（5）- 比特运算

比特运算

比特运算（Bitwise operations）是直接对整数的二进制位进行操作的运算。在Python中，比特运算符可以用来执行按位与（AND）、按位或（OR）、按位异或（XOR）、按位非（NOT）、左移（左移位）和右移（右移位）等操作。

Brian Kernighan算法

Brian Kernighan算法是一种用于高效计算一个整数中二进制表示下1的个数的算法。这个算法的核心思想是利用位运算来快速减少计数的过程。算法基于这样一个观察：对于任意一个非零整数n，n和n-1进行按位与操作（n & (n - 1)）的结果会将n的二进制表示中最右边的一个1变为0。

位运算的技巧

通过与1进行按位与操作可以取得最右位并且判断一个数是奇数还是偶数。通过与(n-1)进行按位与操作可以清零最低位的1。对于十进制整数 x，我们可以用 x & (1 << k) 来判断 x 二进制表示的第 k 位（最低位为第 0 位）是否为 1。

参考文献

https://leetcode.cn/problems/counting-bits/solutions/627418/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/?envType=study-plan-v2&envId=leetcode-75

https://leetcode.cn/problems/minimum-flips-to-make-a-or-b-equal-to-c/solutions/101777/huo-yun-suan-de-zui-xiao-fan-zhuan-ci-shu-by-lee-2/?envType=study-plan-v2&envId=leetcode-75