5

练习是：编写一个函数 setbits(x,p,n,y) 返回 x，其中从位置 p 开始的 n 位设置为 y 的最右边 n 位，其他位保持不变。

我对解决方案的尝试是：

#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));
}

这可能是不正确的，但我在正确的道路上吗？如果没有，我做错了什么？我不确定为什么我不完全理解这一点，但我花了大约一个小时试图想出这个。

谢谢。

4

3 回答 3

5

这是你的算法：

  1. 如果 n 为 0，则返回 x。
  2. 取 1，将其左移 n 次，然后减 1。调用它mask。
  3. 左移掩码 p 次调用 this mask2。
  4. Andx 与 mask2 的倒数。Andy 带掩码，左移 p 次。
  5. Or这两个操作的结果，并返回该值。
于 2010-01-16T03:33:24.950 回答
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 个元素。

我们要做的是替换0 1 1为1 1 1（位串 y 的最后三个元素）。

让我们暂时忘记左移/右移，并将问题可视化如下：

我们需要从位串 y 中获取最后三位数字，即1 1 1

1 1 1直接放在位串4 3 and 2x 的位置下。

替换0 1 1为1 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 and n =3。p 是位置，n 是位集的长度。结果p+1-n给了我们从最右边位开始的位集的偏移量。在这个特定的例子p+1-n = 4 +1-3 = 2中。

所以..如果我们在字符串上左移 2 0 0 0 1 1 1，我们最终得到0 1 1 1 0 0. 如果你把这个字符串放在 x 下，你会注意到它与 x1 1 1的位置对齐4 3 and 2。

我想我终于到了某个地方……我发表的最后一句话是……

将 0 1 1 替换为 1 1 1，同时保持其余位不变...

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

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

对这两个值进行按位或运算可以为我们提供这种情况所需的信息：

1 1 1 1 0 0

但是，如果不是1 1 1, 我们有1 0 1......那么如果我们需要再挖掘一点才能找到我们的“银弹”......

让我们再看一遍上面的两个字符串......

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

所以理想情况下..我们需要 bitstring 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!)

希望这篇长篇文章能帮助人们合理化和解决这些位掩码问题......

谢谢

于 2012-02-07T11:03:50.970 回答
0

请注意，它~0 << i为您提供了一个数字，其中最低有效i位设置为0，其余位设置为1。同样，~(~0 << i)给您一个数字，其最低有效i位设置为1，其余为0。

现在，要解决您的问题：

  1. n首先，您需要一个数字，该数字除了从位置开始的位之外的所有位都p设置为x. 为此，您需要一个掩码，该掩码包含除以position 开头的位1之外的所有位置： np
    1. 此掩码设置了最高（最高有效）位，从 position 处的位开始p+1。
    2. 此掩码还p+1-n设置了最低有效位。
  2. 一旦你有了上面的面具，&这个面具x会给你在步骤 1 中你想要的数字。
  3. 现在，您需要一个具有设置的最低有效n位y、左移位的数字p+1-n。
    1. 您可以轻松地制作一个只设置最低有效n位的掩码，并&使用它y来提取y的最低有效n位。
    2. 然后，您可以按p+1-n位移动该数字。
  4. 最后，您可以按位或 ( |) 步骤 2 和 3.2 的结果来获得您的号码。

清如泥？:-)

（上述方法应该与数字的大小无关，我认为这很重要。）

编辑：看看你的努力：对位n & y没有任何作用n。例如，如果n是 8，您需要 的最后 8 位y，但n & y只会选择y（二进制中的 8 为 1000）的第 4 位。所以你知道这是不对的。类似地，右移x p+1-n时间为您提供了一个最高有效p+1-n位设置为零的数字，其余位由 的最高有效位组成x。这也不是你想要的。

于 2010-01-16T05:39:13.763 回答