k&r 与位操作混淆
练习是： 编写一个函数 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));
}
这可能是不正确的，但是我走的路正确吗？如果不是，我做错了什么？我不确定为什么我不完全理解这一点，但我花了大约一个小时试图想出这一点。
谢谢。
The exercise is:
Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.
My attempt at a solution is:
#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));
}
It's probably incorrect, but am I on the right path here? If not, what am I doing wrong? I'm unsure as to why I don't perfectly understand this, but I spent about an hour trying to come up with this.
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这是您的算法：
mask。和x 与 mask2 的逆。和y 带掩码，左移 p 次。或这两个操作的结果，并返回该值。Here's your algorithm:
mask.mask2.Andx with the inverse of mask2.Andy with mask, and left shift p times.Orthe results of those two operations, and return that value.我认为答案是对 2.9 节中的 getbits 示例进行稍微修改的应用程序。
让我们将其分解如下：
设置
p = 4 和 n =3给出 x 的位串，即0 1 1。它从 4 开始，到 2 结束，跨越 3 个元素。我们想要做的是将
0 1 1替换为1 1 1（位串 y 的最后三个元素）。让我们暂时忘记左移/右移，将问题形象化如下：
我们需要从位串 y 中获取最后三位数字，即
1 1 1放置
1 1 1直接位于位串 x 的位置4 3 和 2下方。将
0 1 1替换为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。因此，让我们看看所需的一系列转换：
这样我们就可以将最后三位数字用于设置目的......
我的第二个陈述是：
可以从第 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对齐。我想我终于有所收获了……我最后的发言是……
现在让我们回顾一下我们的字符串：
对这两个值进行按位或运算可以为我们提供本例所需的内容：
但是如果使用 < 来代替，则会失败code>1 1 1，我们有
1 0 1...所以如果我们需要进一步挖掘才能得到我们的“银弹”...让我们看看再次高于两个字符串...
所以理想情况下...我们需要位串
1 xxx 0 0，其中 x 将与 1 交换。这是对我们有帮助的直觉飞跃。
希望这篇长文章可以帮助人们合理化和解决此类位掩码问题...
谢谢
I think the answer is a slightly modified application of the getbits example from section 2.9.
Lets break it down as follows:
Setting
p = 4 and n =3gives us the bitstring from x which is0 1 1. It starts at 4 and ends at 2 and spans 3 elements.What we want to do is to replace
0 1 1with1 1 1(the last three elements of bitstring y).Lets forget about left-shift/right-shift for the moment and visualize the problem as follows:
We need to grab the last three digits from bitstring y which is
1 1 1Place
1 1 1directly under positions4 3 and 2of bitstring x.Replace
0 1 1with1 1 1while keeping the rest of the bits intact...Now lets go into a little more detail...
My first statement was:
The way to isolate bits from a bitstring is to first start with bitstring that has all 0s.
We end up with
0 0 0 0 0 0.0s have this incredible property where bitwise '&'ing it with another number gives us all 0s and bitwise '|'ing it with another number gives us back that other number.
0 by itself is of no use here...but it tells us that if we '|' the last three digits of y with a '0', we will end up with 1 1 1. The other bits in y don't really concern us here, so we need to figure out a way to zero out those numbers while keeping the last three digits intact. In essence we need the number
0 0 0 1 1 1.So lets look at the series of transformations required:
And this way we have the last three digits to be used for setting purposes...
My second statement was:
A hint for doing this can be found from the getbits example in section 2.9. What we know about positions 4,3 and 2, can be found from the values
p = 4 and n =3. p is the position and n is the length of the bitset. Turns outp+1-ngives us the offset of the bitset from the rightmost bit. In this particular examplep+1-n = 4 +1-3 = 2.So..if we do a left shift by 2 on the string
0 0 0 1 1 1, we end up with0 1 1 1 0 0. If you put this string under x, you will notice that1 1 1aligns with positions4 3 and 2of x.I think I am finally getting somewhere...the last statement I made was..
Lets review our strings now:
Doing a bitwise or on these two values gives us what we need for this case:
But this would fail if instead of
1 1 1, we had1 0 1...so if we need to dig a little more to get to our "silver-bullet"...Lets look at the above two strings one more time...
So ideally..we need the bitstring
1 x x x 0 0, where the x's will be swapped with 1's.Here's a leap of intuition that will help us..
Hope this long post helps people with rationalizing and solving such bitmasking problems...
Thanks
请注意
~0 << i为您提供一个数字，其中最低有效i位设置为0，其余位设置为1。同样，~(~0 << i)给出的数字的最低有效i位设置为1，其余的到0。现在，要解决您的问题：
p开始的n位之外的所有位设置为x 的位。为此，您需要一个掩码，该掩码在除从位置p开始的n位之外的所有位置均由1组成：p+1处的位开始。p+1-n位。&与x将为您提供步骤 1 中所需的数字。y组的n位左移p+1-n位。n位的掩码，并使用&它与y来提取y的最低有效n位。p+1-n位。|) 来获取您的数字。清澈如泥？ :-)
（上述方法应该与数字的大小无关，我认为这很重要。）
编辑：看看你的努力：
n & y不会对n位执行任何操作。例如，如果n为 8，则您需要y的最后 8 位，但n & y只会选择 y 的第 4 位（二进制中的 8 是 1000）。所以你知道那是不对的。同样，右移xp+1-n次会得到一个数字，其最高有效p+1-n位设置为零和其余位由 x 的最高有效位组成。这也不是你想要的。Note that
~0 << igives you a number with the least significantibits set to0, and the rest of the bits set to1. Similarly,~(~0 << i)gives you a number with the least significantibits set to1, and the rest to0.Now, to solve your problem:
nbits that begin at positionpset to the bits ofx. For this, you need a mask that comprises of1in all the places except thenbits beginning at positionp:p+1.p+1-nbits set.&of this mask withxwill give you the number you wanted in step 1.nbits ofyset, shifted leftp+1-nbits.nbits set, and&it withyto extracty's least significantnbits.p+1-nbits.|) the results of step 2 and 3.2 to get your number.Clear as mud? :-)
(The above method should be independent of the size of the numbers, which I think is important.)
Edit: looking at your effort:
n & ydoesn't do anything withnbits. For example, ifnis 8, you want the last 8 bits ofy, butn & ywill just pick the 4th bit ofy(8 in binary is 1000). So you know that can't be right. Similarly, right-shiftingxp+1-ntimes gives you a number that has the most significantp+1-nbits set to zero and the rest of the bits are made of the most significant bits ofx. This isn't what you want either.