代码之家 › 专栏 › 技术社区 › John Rudy

需要帮助理解K&R C第2章中的“getBits()”方法

complement bit-shift bit-manipulation operators c

John Rudy · 技术社区 · 16 年前

在第2章的位运算符部分(第2.9节),我很难理解其中一个示例方法是如何工作的。

提供的方法如下:

unsigned int getbits(unsigned int x, int p, int n) {
    return (x >> (p + 1 - n)) & ~(~0 << n);
}

我们的想法是,对于给定的数字 X ,它将返回 n 位从位置开始磷 ,从右边开始计数(最右边的位是位置0)。给出以下内容 main() 方法:

int main(void) {
    int x = 0xF994, p = 4, n = 3;
    int z = getbits(x, p, n);
    printf("getbits(%u (%x), %d, %d) = %u (%X)\n", x, x, p, n, z, z);

    return 0;
}

输出是:

getbits(63892 (f994), 4, 3) = 5 (5)

我得到了一部分,但在“大局”上遇到了麻烦,主要是因为我不明白的一些细节(没有双关语)。

我特别有问题的部分是补充部分: ~(~0 << n) . 我想我得到第一部分,处理 X 我一直在努力的就是这个部分(然后是面具),以及它是如何结合起来实际检索这些片段的。(我已经用代码和calc.exe检查了我的结果——感谢上帝,它有一个二进制视图!)

有什么帮助吗?

6 回复 | 直到 6 年前

paxdiablo 15 年前

让我们用16位作为例子。在这种情况下,~0等于

1111111111111111

我们离开的时候把这个换了 n 位(在您的情况下为3),我们得到:

1111111111111000

因为 1 左边的S被丢弃 0 S在右边进餐。然后对其进行补充,得出:

0000000000000111

所以这只是一个聪明的方法 n 数字最低有效部分的1位。

您描述的“x位”已经将给定的数字(F994)右移到足够远的位置,因此最低有效的3位就是您想要的。在本例中,您请求的位被“.”字符包围。

ff94             11111111100.101.00  # original number
>> p+1-n     [2] 0011111111100.101.  # shift desired bits to right
& ~(~0 << n) [7] 0000000000000.101.  # clear all the other (left) bits

在那里你有你的部分。塔达!!

Garnet Ulrich 16 年前

我想说,最好的办法是用手把问题解决,这样你就能理解它是如何工作的。

以下是我使用8位无符号int所做的操作。

我们的数字是75,我们需要从位置6开始的4位。对函数的调用将是getbits(75,6,4);
二进制中的75是0100 1011
所以我们创建了一个4位长的掩码,从最低阶位开始,这样就完成了。

~ 0=1111 1111
<<4=1111万
~=0000 1111

好的,我们有面具。

现在,我们把想要的位从数字中推到最低的位,所以我们将二进制75移位6+1-4=3。

0100 1011>>3 0000 1001

现在我们有了一个低阶正确位数和低阶原始位数的掩码。

所以我们和他们

  0000 1001 

& 0000 1111
============

  0000 1001

所以答案是十进制9。

注: 更高阶的半字节恰好都是零,在这种情况下,屏蔽是多余的,但根据我们开始使用的数字的值,它可能是任何东西。

David Grant 11 年前

~(~0 << n) 创建一个将具有 n 右大多数位打开。

0
   0000000000000000
~0
   1111111111111111
~0 << 4
   1111111111110000
~(~0 << 4)
   0000000000001111

把结果和其他东西放在一起会返回其中的内容 n 位。

编辑:我想指出我一直在使用的这个程序员计算器: AnalogX PCalc .

M.M 8 年前

还没有人提到它,但在ANSI C中 ~0 << n 导致未定义的行为。

这是因为 ~0 是负数,左移位负数未定义。

参考文献:C11 6.5.7/4(早期版本的文本相似)

结果 E1 << E2 是 E1 左移 E2 位位置;空出的位用零填充。[…]如果e1有签名类型和非负值,以及 E1 γ 2 ^E2 在结果类型中是可表示的,然后是结果值;否则,行为是未定义的。

在K&R C中,此代码将依赖K&R开发的特定系统类,天真地转换 1 当执行有符号数字的左移位时(并且此代码也依赖于2的补码表示法),左移位位,但其他一些系统不共享这些属性,因此C标准化过程没有定义此行为。

所以这个例子实际上只是作为一个历史的好奇心才有趣,它不应该在1989年以来的任何真实代码中使用(如果不是更早的话)。

Jim 16 年前

使用示例: int x=0xf994,p=4,n=3; int z=获取位(x,p,n);

专注于这一套操作 ~(~0<<n)

对于任何位集(10010011等),您希望生成一个只提取您希望看到的位的“掩码”。所以10010011或0x03,我对xxxxx 011感兴趣。什么是将提取该集的遮罩?00000111现在我想独立于int的sizeof,我将让机器做这个工作,即从0开始,字节机器是0x00,字机器是0x0000,等等。64位机器可以用64位或0x000000000000000表示。

现在应用“not”(~0)并获得11111111
右移(<<)N得到11111000
而“不是”,得到00000111

所以10010011&00000111=00000011
你还记得布尔运算是如何工作的吗?

-2

Surfer Boy 6 年前

在 ANSI C ~0 >> n 导致未定义的行为

//关于左移导致问题的帖子是错误的。

无符号字符m,l;

m=~0>>4;生产255,等于~0,但是,

m=0; L=M>>4;产生的正确值15与以下值相同:

m=255>>4;

左移负极没有问题 ~0 << 无论如何