位操作

#### 任务1：求S除以N（N为2的幂）的余数

**原理**：当$ N $是$ 2 $的幂时，$ S \% N $等价于保留$ S $的二进制表示中低$ k $位（$ N = 2^k $），其余位清零。例如：$ S = 7_{10} = (111)_2 $，$ N = 4 = 2^2 $，则$ S \% N = (111)_2 \& (11)_2 = (11)_2 = 3_{10} $。

**实现**：使用按位与操作：$ S \& (N - 1) $。例如：$ 7 \& (4 - 1) = 7 \& 3 = 3 $。

#### 任务2：判断S是否为2的幂

**原理**：若$ S $是$ 2 $的幂，其二进制表示仅有一个$ 1 $（如$ 8_{10} = (1000)_2 $）。此时$ S - 1 $的二进制为全$ 1 $（如$ 7_{10} = (111)_2 $），因此$ S \& (S - 1) = 0 $。

**实现**：检查$ S \& (S - 1) == 0 $且$ S \neq 0 $。例如：$ 8 \& 7 = 0 $，故$ 8 $是$ 2 $的幂；$ 7 \& 6 = 6 \neq 0 $，故$ 7 $不是。

#### 任务3：关闭S的最后一个位

**原理**：若$ S $的最后一个位为$ 1 $（奇数），则$ S - 1 $会将该位变为$ 0 $，其余低位变为$ 1 $。例如：$ S = 41_{10} = (101001)_2 $，$ S - 1 = 40_{10} = (101000)_2 $。

**实现**：$ S = S \& (S - 1) $（仅当最后一个位为$ 1 $时有效）。例如：$ 41 \& 40 = 40 $。

#### 任务4：打开S的最后一个零位

**原理**：若$ S $的最后一个零位为$ 0 $，则$ S + 1 $会将该位变为$ 1 $，其余低位清零。例如：$ S = 40_{10} = (101000)_2 $，$ S + 1 = 41_{10} = (101001)_2 $。

**实现**：$ S = S \mid (S + 1) $。例如：$ 40 \mid 41 = 41 $。

#### 任务5：关闭S的最后连续的1序列

**原理**：若$ S $的最后连续$ k $个位为$ 1 $，则$ S + 1 $会将这些$ 1 $变为$ 0 $，并在更高位进位。例如：$ S = 39_{10} = (100111)_2 $，$ S + 1 = 40_{10} = (101000)_2 $。

**实现**：$ S = S \& (S + 1) $。例如：$ 39 \& 40 = 32 $。

#### 任务6：打开S的最后连续的0序列

**原理**：若$ S $的最后连续$ k $个位为$ 0 $，则$ S - 1 $会将这些$ 0 $变为$ 1 $，并在更高位借位。例如：$ S = 36_{10} = (100100)_2 $，$ S - 1 = 35_{10} = (100011)_2 $。

**实现**：$ S = S \mid (S - 1) $。例如：$ 36 \mid 35 = 39 $。

#### 任务7：用一行位操作表达式解决UVa 11173（Gray码）

**原理**：Gray码的生成公式为$ G(k) = k \oplus (k >> 1) $，其中$ k $为位置索引。

**实现**：$ \text{gray} = k \oplus (k >> 1) $。

#### 任务8：反转UVa 11173问题（由Gray码求位置k）

**原理**：Gray码转回原数的公式为$ k = \text{gray} \oplus (\text{gray} >> 1) \oplus (\text{gray} >> 2) \oplus \dots $，直到所有位处理完毕。

**实现**：迭代或递归实现，例如：$ k = \text{gray} $；while $ (\text{gray} >>= 1) $ $ k \oplus= \text{gray} $。