算法：位运算深入解析，基础概念与应用

算法：位运算深入解析，基础概念与应用

引用

CSDN

1.

https://m.blog.csdn.net/qq_14829643/article/details/144769388

位运算是一种直接对二进制位进行操作的运算方式，由于计算机中所有数据都是以二进制形式存储的，因此位运算成为了一种非常高效的操作方式。它比其他运算（如加法、减法）更加低级且执行速度快，适用于一些对性能有严格要求的场景，尤其是在处理大量数据时。

接下来将从位运算的基本概念开始，逐步讲解各种常用的位运算操作及其应用场景，并通过具体示例来帮助大家理解位运算的实际使用。

位运算的基本概念

位运算主要包括以下几种常见的操作：与（AND）、或（OR）、异或（XOR）、非（NOT）、左移（<<）和右移（>>）。它们的具体作用如下：

1. 按位与（AND）
   &

按位与运算是将两个数的每一位进行比较，只有当两位都是1时，结果才为1，否则为0。

示例：

  1010 (10)
& 1100 (12)
--------
  1000 (8)

• 1 & 1 = 1
• 0 & 1 = 0
• 1 & 0 = 0
• 0 & 0 = 0

2. 按位或（OR）
   |

按位或运算是将两个数的每一位进行比较，只要两位中有一个是1，结果就为1，只有两位都是0时，结果才为0。

示例：

  1010 (10)
| 1100 (12)
--------
  1110 (14)

3. 按位异或（XOR）
   ^

按位异或运算是将两个数的每一位进行比较，当两位相同则结果为0，当两位不同则结果为1。

示例：

  1010 (10)
^ 1100 (12)
--------
  0110 (6)

4. 按位取反（NOT）
   ~

按位取反是将一个数的每一位反转，0变1，1变0。

示例：

~ 1010 (10) => 0101 (-11)  # 注意：符号位的变化。

5. 左移（<<）

左移运算是将一个数的所有位向左移动指定的位数，右侧补0。左移相当于将数字乘以2的幂。

示例：

  1010 (10)
<< 2
--------
  1000 (40)

6. 右移（>>）

右移运算是将一个数的所有位向右移动指定的位数，对于有符号数，符号位会被处理（负数的符号位根据实现可能会进行扩展，正数则补零）。右移相当于将数字除以2的幂。

示例：

  1010 (10)
>> 2
--------
  0010 (2)

位运算的应用

位运算因其高效性，广泛应用于算法设计中，尤其是在以下场景中：

1. 快速计算和优化

位运算可以替代许多常见的数学运算，从而提高程序的运行速度。例如，左移操作
<<
可以代替乘以2的操作，右移操作

可以代替除以2的操作。

示例：

// 通过左移实现快速乘以2的操作
x := 5
x = x << 1  // 等价于 x = x * 2

2. 判断奇偶性

通过按位与运算，可以快速判断一个数的奇偶性。只需要检查最低位（即最右边一位）是否为1即可。

示例：

// 判断一个数是否为奇数
func isOdd(x int) bool {
    return x & 1 == 1
}

• 例如，
  5
  的二进制表示为
  101
  ，最低位是1，说明它是奇数。

3. 判断数字是否为2的幂

一个整数是2的幂时，它的二进制表示中只有一位是1。通过与运算，可以快速判断一个数是否为2的幂。

示例：

// 判断一个数是否是2的幂
func isPowerOfTwo(x int) bool {
    return x > 0 && (x & (x - 1)) == 0
}

• 例如，
  8
  的二进制表示为
  1000
  ，
  8-1
  的二进制表示为
  0111
  ，
  1000 & 0111
  的结果为
  0
  ，所以
  8
  是2的幂。

4. 交换两个数

通过使用异或运算，可以在不使用临时变量的情况下交换两个数。

示例：

// 交换两个数
func swap(x, y int) (int, int) {
    x = x ^ y
    y = x ^ y
    x = x ^ y
    return x, y
}

5. 统计二进制表示中1的个数

通过位运算，可以高效地统计一个整数的二进制表示中有多少个1。

示例：

// 统计1的个数
func countOnes(x int) int {
    count := 0
    for x > 0 {
        count++
        x = x & (x - 1) // 每次清除最低位的1
    }
    return count
}

• 例如，
  13
  的二进制表示为
  1101
  ，其中有3个1。

6. 位掩码（Bitmask）

位掩码是一种使用位运算来标记特定状态或属性的技巧。例如，使用一个整数的每一位来表示不同的状态。

示例：

const (
    Flag1 = 1 << iota // 0001
    Flag2             // 0010
    Flag3             // 0100
    Flag4             // 1000
)
// 设置标志
flags := Flag1 | Flag3  // 设置 Flag1 和 Flag3
// 检查标志
if flags & Flag1 != 0 {
    fmt.Println("Flag1 is set")
}

7. 位运算在哈希表中的应用

在哈希表实现中，位运算可以用于哈希函数和处理哈希冲突等操作。通过位运算，可以将数据压缩为较小的索引值，提高存储和查找效率。

小结

位运算看似简单，但它的应用非常广泛，尤其是在算法优化、性能提升以及特定计算场景中。掌握位运算不仅可以帮助我们提高代码的执行效率，还可以更好地理解计算机底层的运作机制。

通过学习和实践，我们可以发现，位运算在解决很多常见问题时，是一种非常高效的技术手段。我们想深入理解算法，位运算无疑是必须掌握的一项基本技能。