bit操作面试程序题

掌握位操作，攻克面试难关

在程序员面试中，位操作相关的程序题是常见考点，它能考察候选人对计算机底层原理的理解和编程能力。下面就为大家详细介绍一些常见的位操作面试程序题。

判断奇偶性

判断一个整数是奇数还是偶数，是位操作的基础应用。我们知道，奇数的二进制表示中最低位为 1，偶数的二进制表示中最低位为 0。因此，可以通过与 1 进行按位与操作来判断奇偶性。

示例代码如下：

python

def is_odd(num):

return num & 1 == 1

在这个代码中，`num & 1` 会将 `num` 的二进制表示与 1 进行按位与操作。如果结果为 1，则 `num` 是奇数；如果结果为 0，则 `num` 是偶数。

交换两个数的值

不使用临时变量交换两个数的值，位操作可以轻松实现。利用异或操作的特性：`a ^ a = 0`，`a ^ 0 = a`。

示例代码如下：

python

def swap(a, b):

a = a ^ b

b = a ^ b

a = a ^ b

return a, b

假设 `a = 5`（二进制：101），`b = 3`（二进制：011）。第一次 `a = a ^ b` 后，`a` 的值变为 6（二进制：110）；第二次 `b = a ^ b` 后，`b` 的值变为 5（二进制：101）；第三次 `a = a ^ b` 后，`a` 的值变为 3（二进制：011），从而实现了交换。

计算一个数的二进制中 1 的个数

计算一个整数的二进制表示中 1 的个数，是位操作的经典问题。可以通过不断将该数与自身减 1 的结果进行按位与操作，每次操作会消除最右边的一个 1。

示例代码如下：

python

def count_ones(num):

count = 0

while num:

num = num & (num - 1)

count += 1

return count

例如，对于 `num = 13`（二进制：1101），第一次 `num & (num - 1)` 后，`num` 变为 12（二进制：1100），消除了最右边的 1；继续操作，直到 `num` 变为 0。

判断一个数是否是 2 的幂

如果一个数是 2 的幂，那么它的二进制表示中只有一位是 1。可以利用这个特性，通过 `n & (n - 1)` 来判断。如果结果为 0，则 `n` 是 2 的幂。

示例代码如下：

python

def is_power_of_two(n):

return n > 0 and n & (n - 1) == 0

比如，`n = 8`（二进制：1000），`n - 1 = 7`（二进制：0111），`n & (n - 1) = 0`，所以 8 是 2 的幂。

找出数组中只出现一次的元素

在一个数组中，除了一个元素只出现一次外，其他元素都出现两次。可以利用异或操作的特性，相同元素异或结果为 0，任何数与 0 异或结果为其本身。

示例代码如下：

python

def single_number(nums):

result = 0

for num in nums:

result ^= num

return result

例如，数组 `[2, 3, 2]`，`2 ^ 3 ^ 2 = 3`，所以只出现一次的元素是 3。