标签: 位运算
难度: Easy
给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。
编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。具体插入过程如图所示。
题目保证从 i 位到 j 位足以容纳 M， 例如： M = 10011，则 i～j 区域至少可容纳 5 位。
示例1:
输入：N = 1024(10000000000), M = 19(10011), i = 2, j = 6 输出：N = 1100(10001001100)
示例2:
输入： N = 0, M = 31(11111), i = 0, j = 4 输出：N = 31(11111)
运行时间: 24 ms
内存: 15.9 MB
class Solution:
def insertBits(self, N: int, M: int, i: int, j: int) -> int:
mask_n = 0
for bi in range(i):
mask_n |= 1 << bi
n_low_bits = mask_n & N
n_high_bits = (N>>(j+1)) << (j+1)
M <<= i
N = n_high_bits | M | n_low_bits
return N
这个题解的核心思路是通过位操作将M插入到N的第i到j位。首先，构造一个掩码来保留N中i位以下的位。这个掩码通过对每个位进行迭代，将1左移相应的位数后与mask_n进行或操作来生成。然后，通过将N右移j+1位后再左移j+1位，得到N中j+1位以上的所有位。将M左移i位以对齐到N的第i位。最后，通过将保留的N的高位、调整后的M和保留的N的低位进行或操作，组合成最终结果。
时间复杂度: O(i)
空间复杂度: O(1)
class Solution:
def insertBits(self, N: int, M: int, i: int, j: int) -> int:
mask_n = 0
for bi in range(i):
mask_n |= 1 << bi # 构建从0到i-1位的掩码，以保留N的这些低位
n_low_bits = mask_n & N # 获取N的低位部分
n_high_bits = (N>>(j+1)) << (j+1) # 获取N的高位部分，并确保i到j位为0
M <<= i # 将M左移i位，对齐到N的第i位
N = n_high_bits | M | n_low_bits # 组合N的高位、调整后的M以及N的低位
return N
在构建掩码时，使用迭代方式可以更直观地显示掩码是如何一位一位构建起来的，这对于理解和教学非常有帮助。然而，实际应用中通常会使用更简洁的位运算表达式来生成掩码，例如使用 `(1 << i) - 1` 直接生成从0到i-1位全为1的掩码。这种方法更高效，因为它减少了迭代的需要，直接通过计算得到结果。
为确保在M插入后N的高位处理正确，并防止数据错误，重要的是在处理之前确认N和M的位宽，并适当处理超出的部分。在Python中，整数的位宽不固定（因为Python的整数是动态大小的），但在其他语言如C或Java中，可能需要显式处理溢出。通常，这可以通过使用具有固定位数的类型（例如使用32位整数）并在操作前后应用位掩码来确保只保留有效的位数。例如，如果使用32位整数，可以通过应用掩码 `0xFFFFFFFF` 来确保只保留底部32位。
在题解中，`mask_n`是通过迭代构建的，专门用于保留N的从0到i-1位的位。如果i=0，迭代不执行任何操作，`mask_n`将保持为0，这意味着没有位被保留。这在题解中处理得很好，因为在i=0的情况下，我们不需要保留任何低位。当j等于N的位宽-1时，`n_high_bits`的计算会将N右移后再左移相同的位数，理论上这会清除j+1及之后所有的位。这里的关键是正确计算右移和左移的位数，确保不会错误地保留或丢弃位。在具体实施时，可能需要调整这些计算以适应不同语言或环境的整数位宽限制。