4

C 编程语言的练习 2-7 ：

编写一个函数invert(x,p,n)，返回从反转位置开始x的n位p（即，1 变为 0，反之亦然），其他保持不变。

我理解这样的问题：我有 182 是101(101)10二进制的，括号中的部分必须反转而不改变其余部分。返回值应该是10101010then，即十进制的 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). 我不明白怎么做。

另外，我不知道这段代码有多通用。我的首要任务是让这个案子运作起来。也欢迎在这个问题上提供帮助。

4

5 回答 5

4

((1u<<n)-1)n是在 RHS 处带有“1”位的位掩码。<<p将此块的p位置向左移动。（(p-n)如果你想从左边数，你应该用而不是 p 移动）。

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

当 p 大于 wordsize 时仍然存在问题（移动超过 wordsize 是未定义的），但这应该是调用者的责任;-)

对于101(101)10p=2 和 n=3 的示例：

1u<<n               := 1000
((1u<<n)-1)         := 0111
(((1u<<n)-1) <<p) := 011100
original val    := 10110110
val ^ mask      := 10101010
于 2013-04-01T16:46:42.843 回答
1

我认为您在其中一个班次中遇到了一个不一样的问题（这只是一种预感，我不完全确定）。不过，我会保持简单（我假设索引位置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));
}

注意：在这两种情况下 if p < 0、p >= sizeof(int)*8或p+n < 0的p+n >= sizeof(int)*8结果getbits是未定义的。

于 2013-04-01T16:46:52.573 回答
0

看看 Steve Summit 的“Introductory C programming”和 Ted Jensen 的“At tutorial on pointers and arrays in C”。他们所涵盖的语言与今天的 C 语言有些不同（编程习惯也在演变，机器更大，真正的男人不再编写汇编程序），但他们所说的大部分内容在今天和当时一样真实。肖恩安德森的“Bit twiddling hacks”会让你的眼睛凸出。保证。

于 2013-04-01T19:14:33.513 回答
0

我发现我的实现中出了什么问题（除了num从错误的方向计数）。现在我已经了解了更多关于比特的知识，之后似乎相当明显。

当一个 1 位左移，超出位域的范围时，它被扩展。

   1000 (8) << 1
== 10000 (16)

bitfield << n乘以bitfield2n倍。我的表达式((~bits << (pos+1)) >> num)分别有 5、4 和 3 作为bits、pos和的值num。我将一个几乎 32 位 int 大小的数字乘以 2 两次。

于 2013-04-04T16:48:54.707 回答
0

我的功能怎么样？我觉得很好。

unsigned invert(unsigned x,int p,int n)
{
     return (x^((~(~0<<n))<<p+1-n));
}
于 2014-06-19T03:18:59.577 回答