源内容（英文）
位操作是一种在各种问题中以优化方式获得解决方案的技术。从竞技编程的角度来看，这种技术非常有效。它完全依赖于位运算符，这些运算符直接作用于二进制数或数的位，从而有助于加快实现速度。以下是使用的位运算符：
- 按位与（&）
- 按位或（|）
- 按位异或（^）
- 按位非（!）
计算机程序中的所有数据在内部都以位的形式存储，即数字 0 和 1。
位的表示
在编程中，一个 n 位整数在内部存储为由 n 个位组成的二进制数。例如，C++ 的 int 类型是一个 32 位类型，这意味着每个 int 数由 32 个位组成。
int 数字 43 = 00000000000000000000000000101011
表示中的位从右到左进行索引。要将位表示 bk ···b2 b1 b0 转换为数字，我们可以使用公式
bk2k +…+ b222 + b121 + b020。
例如，1·25+1·23 +1·21 +1·20 = 43。
数的位表示可以是有符号的或无符号的。
通常使用有符号表示，这意味着可以表示负数和正数。
n 位的有符号变量可以包含介于 -2n-1 和 2n-1 – 1 之间的任何整数
C++ 中的 int 类型是有符号类型，因此 int 变量可以包含介于 -231 和 231 – 1 之间的任何整数。
有符号表示中的第一位是数字的符号，非负数为 0，负数为 1，剩余的 n−1 位包含数字的大小。
使用二补数，这意味着数字的相反数是通过首先反转数字中的所有位，然后将数字加一来计算的。
int 数字 −43 的位表示是 11111111111111111111111111010101
在无符号表示中，只能使用非负数，但值的上限更大。
n 位的无符号变量可以包含介于 0 和 2n −1 之间的任何整数。
在 C++ 中，unsigned int 变量可以包含介于 0 和 232 −1 之间的任何整数。
表示之间存在联系：
有符号数 −x 等于无符号数 2n − x。
例如，下面的伪代码片段显示有符号数
x = −43 等于无符号数 y = 232 −43：
!<a href="https://media.geeksforgeeks.org/wp-content/uploads/20230310205206/Screenshot20230310085038.png">imagethe pseudo-code snippet shows that the signed number
如果数字大于位表示的上限，数字将溢出。在有符号表示中，2n-1 – 1 之后的下一个数字是 -2n-1，而在无符号表示中，2n -1 之后的下一个数字是 0。例如，考虑下面的伪代码片段：
!<a href="https://media.geeksforgeeks.org/wp-content/uploads/20230310205419/Screenshot20230310085316.png">image
最初，x 的值是 231 −1。这是可以存储在 int 变量中的最大值，所以 231 −1 之后的下一个数字是 −231 。
在这篇文章中了解更多关于位运算符的信息。以下是一些在编程中经常使用的常见位操作：
位操作：
下表说明了使用位运算符执行操作时的结果。这里 0s 或 1s 分别表示 0 或 1 的序列。
操作
—
X ^ 0s
X ^ 1s
X ^ X
X & 0s
X & 1s
X & X
X \
X
X \
1s
X \
X### 获取位：
此方法用于查找给定数字 N 的特定位置（比如 i）的位。其思想是找到给定数字和 2i 的按位与，可以表示为 (1 << i)。如果返回的值是 1，则第 i 位置的位被设置。否则，它未被设置。
下面是相同的伪代码：
C++
CODEBLOCK_cf9b3b4d
Java
CODEBLOCK_40f7b5cf
Python3
CODEBLOCK_80273c13
C#
CODEBLOCK_31a0694b
Javascript
CODEBLOCK_508b6542
时间复杂度： O(1)
辅助空间： O(1)
设置位：
此方法用于将给定数字 N 的第 i 个位置设置为 1。
方法：
为了设置第 i 个位置的位，我们需要对给定数字和 2i 执行按位或运算，这可以表示为 (1 << i)。
下面是相同的伪代码：
C++
CODEBLOCK_d1c9e657
Java
CODEBLOCK_d86303d8
Python3
CODEBLOCK_cc7fd06f
C#
CODEBLOCK_84e0f85b
Javascript
CODEBLOCK_33cda5d0
时间复杂度： O(1)
辅助空间： O(1)
清除位：
此方法用于清除给定数字 N 的第 i 个位置的位（即将其设置为 0）。
方法：
要清除第 i 个位置的位，我们需要对给定数字和 2i 的按位非执行按位与运算，这可以表示为 ~(1 << i)。
下面是相同的伪代码：
C++
CODEBLOCK_8a60e8cc
Java
CODEBLOCK_f2c49e20
Python3
CODEBLOCK_786293ce
C#
CODEBLOCK_0969bcbc
Javascript
CODEBLOCK_1e4e05db
时间复杂度： O(1)
辅助空间： O(1)
在编程中我们如何使用位操作？
计算整数的二进制表示中 1 的个数：
方法 1（朴素方法）：
- 初始化 count = 0
- 当整数不为 0 时循环。
- 如果 (n & 1) == 1，则执行 count++。
- 右移 n 1 位。
- 返回 count
时间复杂度：O(log n)，其中 n 是给定的整数。
空间复杂度：O(1)
方法 2（Brian Kernighan 算法）：
使用Brian Kernighan算法，可以消除迭代次数等于数字中置位次数的循环。基本上，这个算法跳过了 1 之间的 0。那么这个算法是如何工作的呢？其核心思想是，从数字 n 中减去 1 会翻转最右边的位（包括最右边的 1）并保留其他位不变。所以，如果我们执行 n & (n-1)，它就会从二进制表示中去除最右边的 1。
让我们举个例子，n = 7 (111)2
(n – 1) = 6 (110)2
n & (n-1) = 4 (100)2
现在 n = 4
(n – 1) = 3 (011)2
n & (n-1) = 0 (000)2
现在 n = 0，循环结束。
在这里，我们迭代了 3 次，而在方法 1 中，我们必须迭代 7 次（直到 n 变为 0）。这节省了我们的计算时间。
时间复杂度：O(log n)，其中 n 是给定的整数。
空间复杂度：O(1)
检查一个数字是不是 2 的幂：
一个数字 n 是 2 的幂，当且仅当 n 的二进制表示中正好有一个置位。
例如，4 = 100，8 = 1000，16 = 10000。
我们只需要检查 n 和 (n-1) 的按位与是否等于 0。
让我们再举个例子，n = 4，二进制 100
n – 1 = 3，二进制 011
n & (n-1) = 100 & 011 = 000
因为结果是 0，所以 4 是 2 的幂。
整数溢出：
当我们对整数进行算术运算时，结果是计算的数学值，即使这个值无法用给定数据类型的位数来表示。当无法表示时，它就被称为溢出。在整数运算中，溢出会导致忽略最高有效位，这会导致某些情况下的错误结果。
有符号整数溢出导致未定义的行为，这意味着编译器可以假定溢出永远不会发生，并对其进行优化。
无符号整数溢出导致整数按模 2^n 回绕，其中 n 是存储该整数的位数。
浮点数和双精度数：
计算机使用 IEEE 754 标准来表示浮点数。浮点数使用符号、指数和尾数来表示一个数字。
- 符号：1 位
- 指数：8 位（单精度）/ 11 位（双精度）
- 尾数：23 位（单精度）/ 52 位（双精度）
位操作通常不直接应用于浮点数或双精度数。但是，你可以检查符号位（最高有效位）以确定数字是否为负。
此外，如果你知道表示的确切位模式，可以使用按位运算符来操作浮点数的位，但由于精度和舍入问题，这通常是不鼓励的。