logo标签列表

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

algorithmbinary
108

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

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个回答
1
通过使用JS的字符串操作，可以按照以下方式进行操作；
0b1111011.toString(2).split(/0|(?=.)/).length // returns 6

或者

0b1111011.toString(2).replace("0","").length  // returns 6
1
该函数接受一个整数（int），并返回其二进制表示中1的个数。
public static int findOnes(int number)
{

    if(number < 2)
    {
        if(number == 1)
        {
            count ++;
        }
        else
        {
            return 0;
        }
    }

    value = number % 2;
        
    if(number != 1 && value == 1)
        count ++;

    number /= 2;
        
    findOnes(number);
        
    return count;
}
1

我来到这里，怀着一种强烈的信念，认为我知道这个问题的美丽解决方案。C语言代码：

        short numberOfOnes(unsigned int d) {
            short count = 0;

            for (; (d != 0); d &= (d - 1))
                ++count;

            return count;
        }

但是在我对这个主题进行了一些研究之后（阅读了其他答案：）），我发现了5种更有效的算法。喜欢SO！
甚至有一种针对此任务设计的CPU指令：popcnt。（在this answer中提到）
您可以在此处找到许多算法的描述和基准测试结果。
0
下面的方法也可以计算负数中1的个数。
private static int countBits(int number)    {
    int result = 0;
    while(number != 0)  {
        result += number & 1;
        number = number >>> 1;
    }
    return result;
}

但是，像-1这样的数字在二进制中表示为11111111111111111111111111111111，因此需要进行大量移位。如果您不想对小负数进行如此多的移位，另一种方法是：

private static int countBits(int number)    {
    boolean negFlag = false;
    if(number < 0)  { 
        negFlag = true;
        number = ~number;
    }

    int result = 0;
    while(number != 0)  {
        result += number & 1;
        number = number >> 1;
    }
    return negFlag? (32-result): result;
}
0

Ruby实现

    def find_consecutive_1(n)
      num = n.to_s(2)
      arr = num.split("")
      counter = 0
      max = 0
      arr.each do |x|
          if x.to_i==1
              counter +=1
          else
              max = counter if counter > max
              counter = 0 
          end
          max = counter if counter > max  
      end
      max
    end

    puts find_consecutive_1(439)
0

我不得不在Ruby中进行高尔夫比赛，最终得到了这个结果

    l=->x{x.to_s(2).count ?1}

用法：

l[2**32-1] # 返回32

显然不是很高效，但能解决问题 :)

0
一个Python一行代码。
def countOnes(num):
    return bin(num).count('1')
0

我只能想到一种在O(1)时间内完成此任务的方法...那就是“作弊”，使用物理设备（使用线性或甚至并行编程，我认为极限是O(log(k))，其中k表示数字的字节数）。

但是，你可以很容易地想象出一个物理设备，将每个位连接到输出线上，带有0/1电压。然后，您可以仅在O(1)时间内在“求和”线上电子读取总电压。使用一些基本电路元件可以使这个基本想法更加优雅，以产生您想要的任何形式的输出（例如二进制编码输出），但基本思想是相同的，电子电路将在固定时间内产生正确的输出状态。

我想象中也有可能的量子计算机方案，但如果我们被允许这样做，我认为一个简单的电子电路是更容易的解决方案。

0

我实际上使用了一些巧妙的手法来完成这个：一个只有16个条目的查找表就足够了，你所要做的就是将二进制表示分成四位元组。复杂度实际上是O(1)，我编写了一个C++模板，它专门针对您想要的整数大小（以#位为单位）进行了优化...使其成为常量表达式而不是不确定的。

顺便说一句，您可以利用(i&-i)将返回LS一位比特的事实，并简单地循环，每次剥离lsbit，直到整数为零-但这是一个旧的奇偶校验技巧。

你的O(1)答案假设域是64位。 - Stephen Quan
为什么不使用16位查找表呢？在今天的大多数计算机上，使用64 KB的内存几乎不会被注意到，并且只需要四次查找就可以计算出64位整数的位数。 - Kef Schecter
0
在JavaScript中实现这一点的最佳方法是：
    function getBinaryValue(num){
     return num.toString(2);
    }

    function checkOnces(binaryValue){
        return binaryValue.toString().replace(/0/g, "").length;
    }

其中 binaryValue 是二进制字符串，例如：1100

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接