C语言中整数1位数的计算

lymnna71 于 2023-10-16 发布在其他

关注(0)|答案(2)|浏览(130)

练习2-9.在二进制补码系统中，x &=（x-1）删除x中最右边的1位。解释一下为什么使用这个观察来编写bitcount的更快版本。
练习中提到的bitcount函数是这样的：

/* bitcount:  count 1 bits in x */
int bitcount(unsigned x) {
    int b;
    for (b = 0; x != 0; x >>= 1)
        if (x & 01)
            b++;
    return b;
}

我有点直观地理解了为什么会发生这种情况，但我找不到更严格的答案，无论如何，这是我得出的答案：* 我猜这背后的原因是因为当我们减去1时，我们改变了最右边位的位置，因此当我们按位与x与x-1时，最右边的1消失了，因为x中最右边的1改变了它在x - 1中的位置，因为减去1，例如如果x = 1010，那么x-1 = 1001，当我们按位与它们时，我们得到1000，所以x中最右边的1消失了 *
下面是我实现这个想法的一个简短版本的bitcount：

#include <stdio.h>

int bitcount(unsigned x);

int main() {
    int x, onebits;
    printf("Enter an integer: ");
    scanf("%d", &x);
    onebits = bitcount(x);
    printf("This integer contains %d one bits.", onebits);
    return 0;
}

int bitcount(unsigned x) {
    int b;
    for (b = 0; x != 0; x &= (x - 1))
        ++b;
    return b;
}

如果我犯了错误，有人能纠正我吗？或者提供一个比我更严格的答案？Thanks！：）
这个练习来自里奇和克宁汉的著名著作《C编程语言》。

来源：https://stackoverflow.com/questions/77063536/exercise-about-counting-1-bits-in-an-integer-in-c

2条答案

按热度按时间

pu3pd22g1#

您的代码很好，但对操作工作原因的解释不是很严谨。
二进制数可以以0或1结尾。
如果它以1结尾，减去1就可以将其变为0。当你把这个和原来的数字，所有其他位保持不变，和1 & 0成为0。由于最后1位也是最后一位，因此这将删除最后1位。
如果它以0结尾，减1必须从下一个更高的位“借用”。如果该位也是0，则从下一位借用，依此类推。所有低阶0位都翻转为1，当借用结束时，1位翻转为0。所以如果你从111000开始，借用和翻转的结果是110111。正如您所看到的，所有低阶0位都变成了1，最低的1位变成了0。当你和这些，比翻转和借用系列高的位保持不变，而低位都抵消了0。最终结果是最低的1位被转换为0。

赞(0）回复(0）举报 2023-10-16

dwbf0jvd2#

我有点直观地理解了为什么会发生这种情况，但我找不到更严格的答案，无论如何，这是我得出的答案：我猜这背后的原因是因为当我们减去1时，我们改变了最右边位的位置，因此当我们逐位与x和x-1时，最右边的1消失了，因为x中最右边的1改变了它在x - 1中的位置，因为减去1，例如如果x = 1010，那么x-1 = 1001，当我们按位与它们时，我们得到1000，所以x中最右边的1消失了
在二进制补码计数系统中，有符号和无符号算术的工作方式相同（算术是相同的，唯一的区别是检测到溢出或进位的点），因此二进制数可以表示为二进制的字符串或1和ceros，通常在右边以0或更多0位结束。
如果你减去一个数字，数字的末尾有零，所有这些零将被转换为一（使进位传播到下一个数字），最后，最后一个1位将被改变为零，这是进位从右边传播的结果。进位一旦从它遇到的第一个数字中减去就停止传播，所以对任何数字的结果操作都是所有尾随的零都变成1，最后一个（只有最后一个）变成0。

100101011010100000
100101011010011111
            ^^^^^^  alll these bits change.

如果你现在按位和所有这些位，你会看到所有的 equal 位都被&运算符保持不变，而不同的位都被清零（1 ^ 0 == 0 ^ 1 == 0）这意味着所有的零都保持不变，最后一个1位被清零。QED.（你可以检查如果没有零结束的数字，只有最后一位被改变为零）
另一方面，这将加速您继续的方式，因为它会立即检测1位本身并跳过0位。对于一个有一个小的1位集的数字，速度会更快。
还有另一种（更快）的方法来计算1位：你可以把你的数字看作是一组2位寄存器，提取每个寄存器的左位（这可以并行完成），右移它，并做一个完整的加法到右移，这将在一个镜头中把所有的位对加在一起，给出一组2位的数字（范围为0..2，所以它永远不会溢出），如果你现在重复这个过程，但是考虑到这些位是2位的组，并将数字从2位扩展到4位，我们可以再次把位对的数字加在一起，并继续这样做，直到我们有一个32位的完整寄存器（或64，只是多一步），以寄存器中所有1位的总和结束：这导致了下面的结果（有点晦涩），但比你的循环效率高得多，它有一个更糟糕的最坏情况，当所有的1都必须一个接一个地归零时。

uint64_t sum_of_bits(uint64_t n)
{
    n = ((n & 0xaaaaaaaaaaaaaaaaULL) >>  1) + (n & 0x5555555555555555ULL);
    n = ((n & 0xccccccccccccccccULL) >>  2) + (n & 0x3333333333333333ULL);
    n = ((n & 0xf0f0f0f0f0f0f0f0ULL) >>  4) + (n & 0x0f0f0f0f0f0f0f0fULL);
    n = ((n & 0xff00ff00ff00ff00ULL) >>  8) + (n & 0x00ff00ff00ff00ffULL);
    n = ((n & 0xffff0000ffff0000ULL) >> 16) + (n & 0x0000ffff0000ffffULL);
    n = ((n & 0xffffffff00000000ULL) >> 32) + (n & 0x00000000ffffffffULL);
    return n;
}

在这种方法中，你可以得到平行和的利润。你就开得更快

赞(0）回复(0）举报 2023-10-16

我来回答

C语言中整数1位数的计算

2条答案

相关问题

热门标签

最新问答