位操作破解编码面试

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;

我=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)，与注释不同，仅通过 j-1 清除位 i（参见上面的 mask）
(m << i)将要设置的值移动到需要的位位置
(n & mask) | (m << i) 将移位后的值位与掩码 n

以你的例子：

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

现在，虽然这个示例值产生了正确的结果，但我们可以看到 updateBits() 的实现实际上是错误的，因为 mask 的 left 部分需要 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);

位操作破解编码面试

Bit operations Cracking the Coding Interview

binary

operations

mask