S'S ALGORITHM

位运算：bit操作

基础知识

位操作（Bitwise operation）是计算机中一种对位（bit）进行操作的方法。位操作通常用于对整数的二进制表示进行操作，它们可以快速且有效地执行一些特定的任务，如位移、位与、位或、位异或等。

以下是一些常见的位操作及其用途：

与操作（AND）：用符号 & 表示，将两个操作数的对应位都设为 1 时结果为 1，否则为 0。常用于掩码操作和清除特定位。例如：
```
1010
 & 1100
 --------
1000
```
或操作（OR）：用符号 | 表示，将两个操作数的对应位中只要有一个为 1 时结果为 1，否则为 0。常用于设置特定位。例如：
```
1010
 | 1100
 --------
1110
```
异或操作（XOR）：用符号 ^ 表示，将两个操作数的对应位中只有一个为 1 时结果为 1，否则为 0。常用于比特翻转、检测奇偶性等。例如：
```
1010
 ^ 1100
 --------
0110
```
非操作（NOT）：用符号 ~ 表示，将操作数的每个位取反，即将 0 变为 1，将 1 变为 0。例如：
```
~1010
 ---------
0101
```
左移操作（Left Shift）：用符号 << 表示，将操作数的所有位向左移动指定的位数，右侧补零。例如：1010 << 2 将得到 101000。
右移操作（Right Shift）：用符号 >> 表示，将操作数的所有位向右移动指定的位数，左侧补零或补符号位。例如：1010 >> 2 将得到 0010。

这些位操作常用于优化代码的执行效率，尤其是在需要对位级别进行操作的底层编程或者需要优化计算速度的场景中。但在编写代码时，应当谨慎使用位操作，确保代码的可读性和可维护性。

位操作代码示例

位运算的操作符：

# AND
n = 1 & 1

# OR
n = 1 | 0

# XOR
n = 0 ^ 1

# NOT (negation)
n = ~n

# Bit shifting
n = 1
n = n << 1
n = n >> 1

计算数字中有多少比特的信息，也就是找到所有二进制表达中1的个数。

# Counting Bits
def countBits(n):
    count = 0
    # 当n条件满足还可以进行计算也就是有信息的情况
    while n > 0:
        # 进行位运算，该位上为1
        if n & 1 == 1:
            count += 1
        # 向右平移一个比特
        n = n >> 1 # same as n // 2
    return count