K&R练习中的位运算混淆问题

Question

练习内容如下： 编写一个函数 setbits(x, p, n, y)，将 x 的第 p 位开始的 n 个比特位设置为 y 的右侧 n 个比特位，保留其他比特位不变，并返回结果 x。

我的解决方案如下：

#include <stdio.h>

unsigned setbits(unsigned, int, int, unsigned);

int main(void)
{
    printf("%u\n", setbits(256, 4, 2, 255));
    return 0;
}

unsigned setbits(unsigned x, int p, int n, unsigned y)
{
    return (x >> (p + 1 - n)) | (1 << (n & y));
}

可能不正确，但我这样做是对的吗？如果不是，我做错了什么？我不确定为什么我不能完全理解这个问题，但我花了大约一个小时来想出答案。

谢谢。

- svr

---

完全相同的问题在这里：https://dev59.com/mUnSa4cB1Zd3GeqPM1On - Nick Dandoulakis

关于同一个K＆R问题的问题 - 那里的解释可能会有所帮助。但不完全是相同的问题; 这里的svr已经努力提供了代码。 - Jonathan Leffler

@Jonathan，我同意。这就是为什么我没有投票关闭它的原因。 - Nick Dandoulakis

Answer 1

以下是您的算法：

1. 如果n为0，则返回x。
2. 取1，将其左移n次，然后减去1。将其称为mask。
3. 将mask左移p次，称之为mask2。
4. And x与mask2的反码。And y与mask，并向左移动p次。
5. Or这两个操作的结果，并返回该值。

- Ignacio Vazquez-Abrams

---

无符号整数 setbits(unsigned x, int p, int n, unsigned y) { int mask = (1 << n - 1) - 1; int nask = (mask << p); if (!n) return x; return ((x | ~(nask)) | ((y & mask) << p)); } - svr

比我以前得到的答案看起来更好 :) 无符号 setbits(unsigned) (无符号 x, int p, int n, 无符号 y) {int mask = (1 << n-1) - 1; int nask = (mask << p); 如果 (!n) 返回x; 返回 ((x & ~（nask））| ((y & mask) << p)); } - svr

你对减法/移位的理解是正确的，我会进行修正。但是，在二进制中，“位置”从右侧开始为0，并向左递增。 - Ignacio Vazquez-Abrams

我认为“从p位开始的n位”意味着“从位于位置p的位开始，向右移动n-1位”。看起来https://dev59.com/mUnSa4cB1Zd3GeqPM1On也支持我的观点。 - Alok Singhal

Answer 2

我认为答案是对第2.9节中getbits示例进行轻微修改的应用。

让我们按以下方式分解它：

Let bitstring x be 1 0 1 1 0 0
Let bitstring y be 1 0 1 1 1 1

positions -------->5 4 3 2 1 0

将p = 4 and n =3设为参数，我们得到了从x中提取的二进制字符串为0 1 1。它从第4位开始，到第2位结束，跨越了3个元素。

我们想要做的是用y的最后三个元素1 1 1来替换x中的0 1 1。

暂时忘记左移/右移，把问题可视化如下：

我们需要从y的最后三位中提取数字1 1 1

将1 1 1直接放在x的位置4 3和2下面。

用1 1 1替换0 1 1，同时保持其余的位不变...

现在让我们更详细地了解一下...

我的第一个语句是：

We need to grab the last three digits from bitstring y which is 1 1 1

从一个二进制字符串中分离出一些特定的比特位，需要首先得到一个全是0的二进制字符串。例如：0 0 0 0 0 0。

0具有一种特殊的性质，即对它进行按位'&'运算会产生全0结果，按位'|'运算会还原另一个数值。

但单独使用0在这里没有什么用处...但它告诉我们，如果将y的最后三位与'0'进行按位'|'运算，将得到1 1 1。这里我们不需要关心y中的其他位，因此需要找到一种方法将其它位清零，同时保持最后三位不变。实际上，我们需要的数字是0 0 0 1 1 1。

因此，让我们来看一下所需的一系列转换：

Start with  ->  0 0 0 0 0 0
apply ~0    ->  1 1 1 1 1 1
lshift by 3 ->  1 1 1 0 0 0 
apply ~     ->  0 0 0 1 1 1
& with y    ->  0 0 0 1 1 1 & 1 0 1 1 1 1 -> 0 0 0 1 1 1

这样我们就可以将最后三位数字用于设置目的...

我的第二个陈述是:

将 1 1 1 直接放置在位串 x 的位置 4 3 和 2 下方。

在第 2.9 节中的 getbits 示例中可以找到一个提示。我们知道的有关位置 4、3 和 2 的信息可以从值 p = 4 和 n = 3 中得出。其中，p 是位置，n 是比特集的长度。结果发现 p+1-n 给出了比特集相对于右侧比特的偏移量。在这个特定的示例中，p+1-n = 4+1-3 = 2。

那么...如果我们对字符串 0 0 0 1 1 1 进行左移 2 位，我们得到的就是 0 1 1 1 0 0。如果你把这个字符串放在 x 下面，你会注意到 1 1 1 与 x 的位置 4 3 和 2 对齐。

我想我终于找到了线索...我最后的陈述是...

在保留其余位不变的情况下，用 1 1 1 替换 0 1 1...

现在让我们回顾一下我们的字符串:

x           ->   1 0 1 1 0 0
isolated y  ->   0 1 1 1 0 0

对这两个值进行按位或运算可以得到我们在此情况下所需的结果：

1 1 1 1 0 0 

但是如果我们有的是1 0 1而不是1 1 1，那么这个方法就会失败……所以我们需要更深入挖掘才能找到我们的“银弹”。

让我们再次看一下上面的两个字符串……

x -> bit by bit...1(stays) 0(changes) 1(changes) 1(changes) 0(stays) 0(stays)

理想情况下，我们需要的比特串是1 x x x 0 0，其中x将被替换为1。

这里有一个直觉的突破，将会对我们有所帮助。

Bitwise complement of isolated y -> 1 0 0 0 1 1
& this with x gives us           -> 1 0 0 0 0 0
| this with isolated y           -> 1 1 1 1 0 0 (TADA!)

希望这篇长篇文章能帮助人们理性和解决类似的位掩码问题。感谢您的阅读。

- sc_ray

---

谢谢，这非常有帮助，因为其他答案都没有真正“解释”发生了什么。 - polandeer

这是最好的。花了5分钟登录和点赞。我在理解练习本身方面遇到了问题，你的解释很棒。 - Tanzin

Answer 3

请注意，~0 << i 可以给你一个数字，其中最低有效的 i 位设置为 0，其余位设置为 1。同样地，~(~0 << i) 可以给你一个数字，其中最低有效的 i 位设置为 1，其余位设置为 0。

现在，为了解决您的问题：

首先，您需要一个数字，该数字除了从位置p开始的n位之外，所有位都设置为x的位。 为此，您需要一个掩码，在位置p开始的n位之外的所有位置都包含1：

1. 此掩码具有设置了最高位（最重要）的位，从位置p + 1开始。
2. 此掩码还具有设置了最低有效位p + 1-n个位。

一旦您拥有上述掩码，将其与x进行&运算将为您提供步骤1中所需的数字。

现在，您需要一个数字，该数字具有y的最低有效n位设置为左移p + 1-n位。

1. 您可以轻松制作一个仅具有最低有效n位的掩码，并将其与y进行&运算以提取y的最低有效n位。
2. 然后，您可以将此数字向左移动p + 1-n位。

最后，您可以按位或（|）步骤2和3.2的结果以获得您的数字。

一清二楚了吗？:-)

(上述方法应该独立于数字的大小，这我认为很重要。)

编辑：看看你的努力：n&y不会对n位做任何事情。例如，如果n是8，您想要y的最后8位，但n&y只会选择y的第4位（8在二进制中是1000）。所以你知道那肯定不对。同样，将x右移p+1-n次会给您一个数字，该数字的最高有效p+1-n位设置为零，其余位由x的最高有效位组成。这也不是你想要的。

- Alok Singhal