4

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

编写一个函数invert(x,p,n),返回从反转位置开始xnp(即,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 < 0p >= sizeof(int)*8p+n < 0p+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 作为bitspos和的值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 回答