LeetCode 3226. 使两个整数相等的位更改次数

. - 力扣（LeetCode）

题目

给你两个正整数 n 和 k。你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。

返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。

• 示例 1：
  • 输入： n = 13, k = 4
  • 输出： 2
  • 解释：最初，n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2，我们可以改变 n 的第一位和第四位。结果整数为 n = (0100)2 = k。
• 示例 2：
  • 输入： n = 21, k = 21
  • 输出： 0
  • 解释：n 和 k 已经相等，因此不需要更改。
• 示例 3：
  • 输入： n = 14, k = 13
  • 输出： -1
  • 解释：无法使 n 等于 k。

解题方案

1. 逐位遍历

依次取n和k最后一位，进行比较

• 如果last_n == last_k， 则不需要修改，继续遍历
• 如果lask_n != last_k:
  • 如果last_n == 1, last_k == 0, 则需要改变操作，操作数+1
  • 如果last_n == 0, last_k == 1, 则无法通过指定操作使n变成k, 直接返回-1

class Solution:def minChanges(self, n: int, k: int) -> int:if n < k:return -1if n == k:return 0mod = 0while k > 0 or n > 0:last_n = n & 1 # 取n的最后一位last_k = k & 1 # 取k的最后一位n = n >> 1k = k >> 1if last_n == last_k:continueelif last_k == 1:return - 1else:mod += 1 return mod

分析复杂度

• 时间复杂度是n和k位数的最大值： 

• 空间复杂度是

2. 位操作

如果把n和k的二进制为1的位分别看做一个集合，那么k应该是n的一个子集。

1. 按位或操作，如果操作结果等于k，则n可以通过修改某些位置上1为0得到k；反之则不能，直接返回-1.

2. 已知n可以通过修改某些位置上1为0得到k，接下来进行异或操作（n和k不同的位为1，即需要修改的位为1），统计操作结果中1的位数即可

class Solution:def minChanges(self, n: int, k: int) -> int:return (n ^ k).bit_count() if (n & k) == k else -1

分析复杂度

• 时间复杂度 O(1)
• 空间复杂度 O(1) 

Python中的位操作

在Python中，位操作（bitwise operations）是直接对二进制位进行操作的技术。这些操作对于需要高效处理二进制数据、执行低级硬件控制或者优化算法的场景非常有用。以下是一些常见的位操作符及其用法：

1. 按位与 (&)：

将两个数的每一个对应位进行与操作（两位都为1时结果为1，否则为0）。

a = 5  # 0101  
b = 3  # 0011  
result = a & b  # 0101 & 0011 = 0001  
print(result)  # 输出 1

取数字二进制中的最后一位

a = 5 # 二进制为 101
mask = 1
last_bit = a & mask # 结果为1

 

2. 按位或 (|)：

将两个数的每一个对应位进行或操作（只要有一位为1，结果就是1）。

a = 5  # 0101  
b = 3  # 0011  
result = a | b  # 0101 | 0011 = 0111  
print(result)  # 输出 7

3. 按位异或 (^)：

将两个数的每一个对应位进行异或操作（两位相同时为0，不同时为1）。

a = 5  # 0101  
b = 3  # 0011  
result = a ^ b  # 0101 ^ 0011 = 0110  
print(result)  # 输出 6

4. 按位取反 (~)：

对操作数的每一位取反（0变1，1变0）。注意，Python中的整数是有符号的，取反后会得到一个负数。

a = 5  # 0101  
result = ~a  # ~0101 = 1010 (在补码表示中为 -6)  
print(result)  # 输出 -6

5. 左移 (<<)：

将操作数的二进制表示向左移动指定的位数，右边补0。

a = 5  # 0101  
result = a << 1  # 0101 << 1 = 1010  
print(result)  # 输出 10

6. 右移 (>>)：

将操作数的二进制表示向右移动指定的位数，左边补符号位（正数补0，负数补1）。

a = 5  # 0101  
result = a >> 1  # 0101 >> 1 = 0010  
print(result)  # 输出 2  b = -5  # 在补码表示中为 11111111111111111111111111111011  
result = b >> 1  # 11111111111111111111111111111011 >> 1 = 11111111111111111111111111111101  
print(result)  # 输出 -3

7. 统计数字中1的位数(bit_count)

在Python中，bit_count() 是 int 类型的一个方法，用于计算一个整数的二进制表示中设置为1的位的数量。这个方法在Python 3.10及更高版本中可用。

number = 29  # 二进制表示为 11101  
bit_count = number.bit_count()  
print(bit_count)  # 输出 4，因为二进制表示中有4个位是1

实际应用

• 权限管理：位操作常用于权限管理中，例如使用每个位表示一个特定的权限。
• 低级别硬件控制：在需要直接操作硬件寄存器或内存时，位操作是必不可少的。
• 性能优化：在某些算法中，使用位操作可以显著提高性能，因为它们直接操作二进制数据，减少了计算开销。

注意事项

• Python中的整数是任意精度的，但在进行位操作时，通常会将其视为固定宽度的二进制数（取决于操作系统和Python版本，通常是32位或64位）。
• 当使用右移操作时，特别是对于负数，需要注意补位的方式（符号位扩展）。