K&R练习2-7中的位反求函数

Question

C语言的练习2-7：

编写一个函数invert(x,p,n)，返回x，其n位开始于p倒置位置(即1改为0，反之亦然)，其余部分则保持不变。

我理解的问题是这样的:我有182，在二进制中是101(101)10，括号中的部分必须倒置，而不改变其余的部分。返回值应该是10101010，小数点为170。

以下是我的尝试：

#include <stdio.h>

unsigned int getbits(unsigned int bitfield, int pos, int num);
unsigned int invert(unsigned int bitfield, int pos, int num);

int main(void)
{
    printf("%d\n", invert(182, 4, 3));
    return 0;
}

/* getbits: get num bits from position pos */
unsigned int getbits(unsigned int bitfield, int pos, int num)
{
    return (bitfield >> (pos+1-n)) & ~(~0 << num);
}

/* invert: flip pos-num bits in bitfield */
unsigned int invert(unsigned int bitfield, int pos, int num)
{
    unsigned int mask;
    unsigned int bits = getbits(bitfield,pos,num);

    mask = (bits << (num-1)) | ((~bits << (pos+1)) >> num);

    return bitfield ^ mask;
}

(在我看来)这似乎是对的，但是invert(182, 4, 3)输出536870730。getbits()工作得很好(它是直接从书中得到的)。我在分配给y的表达式中写下了发生的事情：

(00000101 << 2) | ((~00000101 << 5) >> 3)    -- 000000101 is the part being flipped: 101(101)10
       00010100 | ((11111010 << 5) >> 3)
       00010100 | (01000000 >> 3)
       00010100 | 00001000
= 00011100

  10110110 (182)
^ 00011100
----------
= 10101010 (170)

应该是对的，但事实并非如此。我发现问题出在这里：((~xpn << (p+1)) >> n)。我不知道是怎么回事。

而且，我也不知道这段代码有多普遍。我的第一要务就是让这个案子正常运作。在这个问题上的帮助也是欢迎的。

Answer 1

((1u<<n)-1)是一个位掩码，在RHS上有n '1‘位。<<p将这个p位置块移到左边。(如果您想从左边计数，则应该使用(p-n)而不是p)。

return val  ^ (((1u<<n)-1) <<p) ;

当p大于字大小时仍然存在问题(移位大于未定义的字大小)，但这应该是调用者的响应性;-)

例如，101(101)10与p=2和n=3：

1u<<n               := 1000
((1u<<n)-1)         := 0111
(((1u<<n)-1) <<p) := 011100
original val    := 10110110
val ^ mask      := 10101010

Answer 2

我认为你在其中一次轮班中有一个不合时宜的问题(这只是一个预感，我不完全确定)。尽管如此，我还是会保持简单(假设索引位置p从LSB开始，即p=0是LSB)：

unsigned int getbits(unsigned int x, int p, int n) {
  unsigned int ones = ~(unsigned int)0;
  return x ^ (ones << p) ^ (ones << (p+n));
}

编辑:如果您需要p=0作为MSB，只需倒转(因为ones被定义为unsigned int)，这是正确的：

unsigned int getbits(unsigned int x, int p, int n) {
  unsigned int ones = ~(unsigned int)0;
  return x ^ (ones >> p) ^ (ones >> (p+n));
}

注意:在这两种情况下，如果p < 0、p >= sizeof(int)*8、p+n < 0或p+n >= sizeof(int)*8都没有定义getbits的结果。

Answer 3

看看史蒂夫峰会的“介绍性C程序设计”和Ted的“关于C中指针和数组的教程”。它们所涵盖的语言与今天的C有一点不同(编程习惯也在进化，机器要大得多，真正的人不再写汇编程序了)，但他们所说的很多话都和当时的情况一样。肖恩·安德森的“旋转手柄”会让你的眼睛凸起。有保证。