插入
难度:
标签:
题目描述
You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.
Example1:
Input: N = 10000000000, M = 10011, i = 2, j = 6 Output: N = 10001001100
Example2:
Input: N = 0, M = 11111, i = 0, j = 4 Output: N = 11111
代码结果
运行时间: 24 ms, 内存: 15.9 MB
/*
* Solution Idea using Java Stream:
* 1. Use bitwise operations to clear and set the bits as needed.
* 2. Java Streams are not typically used for bitwise operations, but the approach remains the same.
*/
import java.util.stream.IntStream;
public class SolutionStream {
public int insertBits(int N, int M, int i, int j) {
int allOnes = ~0; // allOnes will be a sequence of all 1s
int left = allOnes << (j + 1); // 1s before position j, then 0s
int right = (1 << i) - 1; // 1s after position i
int mask = left | right; // All 1s, except for 0s between i and j
// Clear the bits j through i then put M in there
int nCleared = N & mask; // Clear bits j through i.
int mShifted = M << i; // Move M into the correct position.
// Combine cleared N and shifted M
return IntStream.of(nCleared, mShifted).reduce((a, b) -> a | b).getAsInt();
}
}
解释
方法:
这个题解的核心思路是通过位操作将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)
代码细节讲解
🦆
在构建掩码时，为何选择从0到i-1位迭代而不是直接使用位运算表达式生成掩码？
▷🦆
如何确保在插入M后，N的位数如果超过原始位数时，高位的处理正确且不会引起数据错误？
▷🦆
在题解中提到的`mask_n`和实际操作中的掩码构造有何区别，特别是在处理边界（即i=0或j等于N的位宽-1）时？
▷