面试题 05.01 插入
给定两个整型数字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)
题目分析
简单的位运算问题，只需要把 N 的 i 到 j 位都置 0 后再和 M 左移 i 位的结果进行按位或即可
在 Java 语言中，int 类型的左移位数
n≥32时，JVM 会将n对32取模，以确保左移的位数在 n 在 [0,31] 之间。因此，需使用0xffffffff << j << 1
public int insertBits(int N, int M, int i, int j) {
int mask = (0xffffffff << j << 1) + ((1 << i) - 1);
return N & mask | M << i;
}
位运算基础知识
-
判断奇偶：
-
奇：
(x & 1) == 1⟺(x & 1) != 0 -
偶：
(x & 1) == 0⟺(x & 1) != 1
-
-
乘（或除）以 2 的幂次：
-
x >> n ⟺ x / 2^n -
x << n ⟺ x * 2^n
-
-
去除最后一位 1：
x & (x - 1) -
得到最后一位 1：
x & -x -
判断 2 的幂次：
x & (x - 1) == 0 -
交换两个数：
a ^= b; b ^= a; a ^= b; -
交换符号：
~x + 1⟺-x -
取绝对值：
(x ^ x >> size(x) - 1) - (x >> size(x) - 1)⟺x < 0 ? -x : x -
构造 n 个 1：
(1 << n) - 1 -
将最左边的 n 位清零：
x & (~0 << n) -
获取 x 的第 n 位值（0 或 1）：
(x >> n) & 1 -
获取 x 的第 n 位的幂值：
x & (1 << n) -
仅将第 n 位置为 1：
x | (1 << n) -
仅将第 n 位置为 0：
x & (~(1 << n)) -
将 x 最高位至第 n 位（含）清零：
x & ((1 << n) - 1) -
将第 n 位至第 0 位（含）清零：
x & (~((1 << (n + 1)) - 1)) -
取反第 n 位：
x ^ (1 << n) -
异或满足交换律、结合律：
a ^ b ^ a = b ^ (a ^ a) = b ^ 0 = b
