binary - 位运算破解编码面试

Question

我一直在尝试解决 CTCI 中的第一个问题，其中涉及位操作，但我只是无法弄清楚作者如何在他的最终解决方案中准确地制作掩模。有人可以解释“int left”、“int right”和“int mask”的计算吗？很高兴看到这些行专门针对他提供的示例计算了什么。

问题是: 给定两个 32 位数字 N 和 M，以及两个位位置 i 和 j。写一个 方法将 N 中 i 和 j 之间的所有位设置为 M(例如，M 成为 N 位于 i 并开始于 j)。 例子: 输入:N = 10000000000，M = 10101，i = 2，j = 6 输出:N = 10001010100

public static int updateBits(int n, int m, int i, int j) {
int max = ~0; /* All 1’s */

// 1’s through position j, then 0’s
int left = max - ((1 << j) - 1);

// 1’s after position i
int right = ((1 << i) - 1);

// 1’s, with 0s between i and j
int mask = left | right;

// Clear i through j, then put m in there
return (n & mask) | (m << i);
}

Answer 1

explain the calculations for "int left", "int right", and "int mask"

// 1’s through position j, then 0’s
int left = max - ((1 << j) - 1);

• (1 << j) 仅将位置 j 处的位设置为 1
• ((1 << j) - 1) (减去 1 )将位置 j 下面(右侧)的所有 j 位设置为 1
• max - ((1 << j) - 1)(从所有 1 中减去)产生上述的按位补码，i。 e.上面(左边)的所有位(包括位置 j)设置为 1 ，下面的 j 位设置为 0

e. G。

j          1<<j            (1<<j)-1       ~0-((1<<j)-1)
-------------------------------------------------------
0      000000000001      000000000000      111111111111
1      000000000010      000000000001      111111111110
2      000000000100      000000000011      111111111100
3      000000001000      000000000111      111111111000
4      000000010000      000000001111      111111110000
5      000000100000      000000011111      111111100000
6      000001000000      000000111111      111111000000
...

// 1’s after position i
int right = ((1 << i) - 1);

• (1 << i) 仅将位置 i 处的位设置为 1
• ((1 << i) - 1) (减去 1 )将位置 i 下面(右侧)的所有 i 位设置为 1

e. G。

i          1<<i            (1<<i)-1
-------------------------------------
0      000000000001      000000000000
1      000000000010      000000000001
2      000000000100      000000000011
...

// 1’s, with 0s between i and j
int mask = left | right;

i = 2，j = 6:

left      111111000000
right     000000000011
|         ------------
mask      111111000011

// Clear i through j, then put m in there
return (n & mask) | (m << i);

• (n & mask) 与注释不同，仅清除 i 到 j -1 位(请参阅上面的 mask)
• (m << i) 将要设置的值移动到所需的位位置
• (n & mask) | (m << i) 将移位后的值位与掩码 n 进行或运算

以你的例子:

n       010000000000
mask    111111000011
&       ------------
n&mask  010000000000
m<<i    000001010100
|       ------------
        010001010100

现在，虽然这个示例值产生了正确的结果，但我们可以看到 updateBits() 的实现实际上是错误的，因为 left 的 mask 部分只需要 1 位到 和 的左边不需要包括位置 j ，因为位位置 j 属于要屏蔽掉的子字符串。错误表明e。 G。值为 n = 11111111111、m = 00000、i = 2、j = 6:

n       011111111111
mask    111111000011
&       ------------
n&mask  011111000011
m<<i    000000000000
|       ------------
        011111000011

值m仅被放入i至j-1位位置。

可以通过更改来纠正错误

int left = max - ((1 << j) - 1);

至

int left = max - ((1 << j+1) - 1);