在二进制表示中计算1的数量

Question

在二进制表示中计算1的数量

algorithmbinary

108

如果您有足够的内存来处理，高效计算一个数字的二进制表示中1的数量的方法是O(1)。这是我在一个在线论坛上找到的面试问题，但没有答案。有人能提供一些建议吗？我无法想出如何在O(1)时间内完成。

- TimeToCodeTheRoad

2

所以这个问题想要让你作弊 - “足够”的内存很容易比可观测宇宙中的原子数量还要多。 - harold

这不就是一个长度为MAX_INT的数组吗？ - Boris Treukhov

1

如果我们有一个数组[0..MAX_INT-1]，其中索引是输入的实际数字，数据是该数字中1的数量（假设它是通过内容可寻址存储器http://en.wikipedia.org/wiki/Content-addressable_memory实现的），那么它不就是O(1)吗？ - Boris Treukhov

2

这可能是模型面试解决方案，尽管我认为它不会满足纯粹主义者，因为它受机器可寻址内存的数据宽度（例如64位）的限制。对于大于2^64的数字，它将无法工作，而且问题并没有强制执行此限制。如果问题修订为“64位数字”，那么是的，这是一个好的解决方案。 - Tim Gee

1

另一方面，对于64位数字，旧的位计数方法也是O(1)，几乎不使用内存。 - Daniel Fischer

22个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ben · Answer 1

使用Python或其他编程语言将数字转换为二进制字符串，然后使用字符'0'进行分割以去除0，最后合并字符串并获取其长度。

len(''.join(str(bin(122011)).split('0')))-1

- parasrish · Answer 2

两种方法：

/* Method-1 */
int count1s(long num)
{
    int tempCount = 0;

    while(num)
    {
        tempCount += (num & 1); //inc, based on right most bit checked
        num = num >> 1;         //right shift bit by 1
    }

    return tempCount;
}

/* Method-2 */
int count1s_(int num)
{
    int tempCount = 0;

    std::string strNum = std::bitset< 16 >( num ).to_string(); // string conversion
    cout << "strNum=" << strNum << endl;
    for(int i=0; i<strNum.size(); i++)
    {
        if('1' == strNum[i])
        {
            tempCount++;
        }
    }

    return tempCount;
}

/* Method-3 (algorithmically - boost string split could be used) */
1) split the binary string over '1'.
2) count = vector (containing splits) size - 1

用法：

    int count = 0;

    count = count1s(0b00110011);
    cout << "count(0b00110011) = " << count << endl; //4

    count = count1s(0b01110110);
    cout << "count(0b01110110) = " << count << endl;  //5

    count = count1s(0b00000000);
    cout << "count(0b00000000) = " << count << endl;  //0

    count = count1s(0b11111111);
    cout << "count(0b11111111) = " << count << endl;  //8

    count = count1s_(0b1100);
    cout << "count(0b1100) = " << count << endl;  //2

    count = count1s_(0b11111111);
    cout << "count(0b11111111) = " << count << endl;  //8

    count = count1s_(0b0);
    cout << "count(0b0) = " << count << endl;  //0

    count = count1s_(0b1);
    cout << "count(0b1) = " << count << endl;  //1