位运算

位运算是对整数在二进制位层面上进行直接操作的运算。它在性能敏感的程序中尤其重要，例如操作系统、嵌入式系统、加密算法等领域，通常比普通的算术运算更高效。

1. 按位“或”运算的性质（OR）

对于任意两个整数 A 和 B，按位或运算（A | B）具有以下几条重要性质：

1.1. 自反性（Idempotence）

任何数与自身做按位或运算，结果仍然是自身。例如：

• 5 | 5 = 5

1.2. 单调性（Monotonicity）

$$A \leq B \implies A | C \leq B | C \quad \text{对于任意的} C$$

这意味着，如果 A 小于 B，则 A 与任意数 C 做按位或运算的结果将不大于 B 与 C 的按位或结果。直观来说，按位或运算不会缩小数值。

1.3. 与任意元素按位或运算，结果大于等于自身

$$A | B \geq A$$

按位或操作将 A 中的 0 变为 1，不会使 1 变回 0，因此 A | B 的每一位都大于或等于 A 的相应位。

1.4. 交换律（Commutativity）

$A | B = B | A$

按位或运算是交换的，即 A 与 B 按位或运算的结果与顺序无关。

1.5. 结合律（Associativity）

$(A | B) | C = A | (B | C)$

按位或运算是结合的，即对多个数进行按位或时，操作的顺序可以任意调整。

1.6. 单位元（Identity Element）

$$A | 0 = A$$

任意数与 0 做按位或运算，结果仍然是该数本身。

1.7. 吸收律（Absorption）

$$A | (A \& B) = A$$

任何数与它与另一个数按位与（&）的结果做按位或，结果等于原数。这个性质的意思是，按位或操作“吸收”了按位与的结果。

1.8. 按位或与按位与的分配律（Distributivity）

$$A | (B \& C) = (A | B) \& (A | C)$$

按位或和按位与之间存在分配律，类似于普通算数运算中的分配律。

---

2. 按位“与”运算的性质（AND）

按位与运算（A & B）也有一些类似的性质：

2.1. 自反性（Idempotence）

A & A = A

任何数与自身做按位与运算，结果仍然是自身。

2.2. 交换律（Commutativity）

A & B = B & A

按位与运算是交换的。

2.3. 结合律（Associativity）

(A & B) & C = A & (B & C)

按位与运算是结合的。

2.4. 单位元（Identity Element）

A & 1 = A

任意数与 1 做按位与运算，结果仍然是该数本身。注意，1 在二进制中相当于所有位都为 1。

2.5. 零元（Null Element）

A & 0 = 0

任意数与 0 做按位与运算，结果为 0。这是因为与 0 按位与运算的任何结果都会是 0。

2.6. 吸收律（Absorption）

A & (A | B) = A

按位与与按位或之间也有吸收律，类似于上面按位或的吸收律。

---

3. 按位异或运算的性质（XOR）

按位异或运算（A ^ B）也具有一些特别的性质：

3.1. 自反性（Idempotence）

A ^ A = 0

任何数与自身做按位异或，结果为 0。

3.2. 交换律（Commutativity）

A ^ B = B ^ A

按位异或是交换的。

3.3. 结合律（Associativity）

(A ^ B) ^ C = A ^ (B ^ C)

按位异或是结合的。

3.4. 单位元（Identity Element）

A ^ 0 = A

任何数与 0 做按位异或运算，结果仍然是该数本身。

3.5. 对称性（Symmetry）

A ^ B = B ^ A

按位异或是对称的。

---

4. 按位“非”运算的性质（NOT）

按位非（~）运算的性质相对简单：

4.1. 自反性（Idempotence）

$$\sim (\sim A) = A$$

对某个数取两次按位非，结果是原数。

4.2. 按位非操作

按位非操作对二进制数的每一位取反，即 0 变 1，1 变 0。

---

5. 位运算的应用

位运算在编程中非常有用，特别是在涉及到大量的数值操作、标志位管理、内存优化等场景。以下是一些常见的应用：

• 判断某个数是否为偶数：x & 1 == 0
• 判断某个数是否为 2 的幂：x & (x - 1) == 0
• 提取某一位：(x >> n) & 1，获取第 n 位的值。
• 设置某一位：x | (1 << n)，设置第 n 位为 1。
• 清除某一位：x & ~(1 << n)，清除第 n 位。
• 反转某一位：x ^ (1 << n)，反转第 n 位。

位运算的基本操作

Java 和大多数编程语言支持以下几种常见的位运算：

1. 按位与（AND）：&

   • 规则：两个操作数的相同位置上的位都为 1，结果才为 1。

     5 & 3

     • 5 的二进制是 0101
     • 3 的二进制是 0011
     • 结果：0101 & 0011 = 0001 → 1

2. 按位或（OR）：|

   • 规则：两个操作数的相同位置上的位只要有一个为 1，结果就为 1。

     5 | 3

     • 5 的二进制是 0101
     • 3 的二进制是 0011
     • 结果：0101 | 0011 = 0111 → 7

3. 按位异或（XOR）：^

   • 规则：两个操作数的相同位置上的位不同，结果为 1，相同则为 0。

     5 ^ 3

     • 5 的二进制是 0101
     • 3 的二进制是 0011
     • 结果：0101 ^ 0011 = 0110 → 6

4. 按位非（NOT）：~

   • 规则：对每一位取反，0 变成 1，1 变成 0。注意，这个操作会影响符号位，在 Java 中对 int 取反后是 32 位。

     ~5

     • 5 的二进制是 00000000000000000000000000000101
     • 结果：~5 = 11111111111111111111111111111010 → -6（二进制补码表示）

5. 位移操作：

   • 左移（<<）：将数字的所有位向左移动指定的位数，右侧用0补充。

     5 << 1

     • 5 的二进制是 0101
     • 左移一位：1010 → 10

   • 右移（>>）：将数字的所有位向右移动指定的位数，对于正数，用0填补；对于负数，符号位保持不变。

     5 >> 1

     • 5 的二进制是 0101
     • 右移一位：0010 → 2

   • 无符号右移（>>>）：与右移类似，但是对负数无符号右移时会将符号位填充为0。

     -5 >>> 1

     • -5 的二进制（补码表示）是 11111111111111111111111111111011

   • 无符号右移一位：01111111111111111111111111111101 → 2147483642

---

位运算的技巧与应用

1. 快速计算乘法与除法（2 的幂）

   • 左移：相当于乘以 2 的某个次幂。例如，x << n 等价于 x * 2^n。

      int x = 5;
     int result = x << 2;  // 相当于 5 * 4 = 20

   • 右移：相当于除以 2 的某个次幂。例如，x >> n等价于 x / 2^n。

     int x = 20;
     int result = x >> 2;  // 相当于 20 / 4 = 5

2. 判断奇偶数

   • 奇数：x & 1 为 1 时，表示 x 是奇数。

   • 偶数：x & 1为 0时，表示x是偶数。

     int x = 5;
     boolean isOdd = (x & 1) == 1;  // 5 是奇数，结果为 true

3. 判断是否是 2 的幂

   • 一个数如果是 2 的幂，则它与它的前一个数按位与结果为 0。例如，x 是 2 的幂，当且仅当 x & (x - 1) == 0。

          int x = 8;
          boolean isPowerOfTwo = (x & (x - 1)) == 0;  // 8 是 2 的幂，结果为 true
        
     4. **交换两个数**
     
        - 利用异或操作可以在不使用临时变量的情况下交换两个数。
     
          ```java
          int a = 5, b = 3;
          a = a ^ b;  // a = 6
          b = a ^ b;  // b = 5
          a = a ^ b;  // a = 3
          // 交换后，a=3, b=5

4. 设置某一位

   • 使用按位或操作来设置某一位为1

          int x = 5;   // 0101
          int result = x | (1 << 2);  // 设置第 2 位为 1 -> 0111
        
     6. **清除某一位**
     
        - 使用按位与操作和按位非操作清除某一位。
     
          ```java
          int x = 5;   // 0101
          int result = x & ~(1 << 2);  // 清除第 2 位 -> 0001

5. 反转某一位

   • 使用按位异或操作来反转某一位。

     int x = 5;   // 0101
     int result = x ^ (1 << 2);  // 反转第 2 位 -> 0001

6. 求平均数不带小数

   • 位运算(a + b) >> 1

   • 使用了位运算来高效地计算两个整数的平均值。通过按位与运算找到不进位的部分，按位异或运算找出进位的部分，然后将进位部分右移并与不进位部分相加，最终得到 a 和 b 的平均值。这种方法比直接使用 (a + b) / 2 更加高效。

     int result = ((a & b) + (a ^ b) >> 1) ;  

7. 清零最低位的1

   • 检查 n 是否是 2 的幂：如果 n & (n - 1) == 0，那么 n 是 2 的幂。

   • 清除 n 中最低位的 1。

     int result = n & (n - 1) ;  

---

位运算的常见应用场景：

1. 图像处理：位运算用于像素的颜色深度处理和图像操作。
2. 网络协议：许多网络协议（如 IP 地址、子网掩码）都依赖于位运算来处理二进制数据。
3. 压缩算法：一些数据压缩算法利用位运算优化空间存储。
4. 加密与解密：位运算被广泛应用于数据加密算法中（如 XOR 操作）。

位运算是计算机科学中非常重要且高效的工具，它使得很多操作能够以最小的成本完成，尤其在性能要求高的场景下，掌握位运算能大大提高程序的效率。