blocks|key|332830|text|这就是Hamming+weight的问题。人口计数。该链接提到了有效的实现。引用：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|332831|332832|有无限的内存，我们可以简单地创建一个包含每个64位整数|blockquote|332833|
的汉明权重的大型查找表|332834|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Hamming_weight^0|3|E|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@$A|S|B|T|1|U]]|C|$]]|$1|D|3|-4|5|6|7|V|8|@]|9|@]|C|$]]|$1|E|3|F|5|G|7|W|8|@]|9|@]|C|$]]|$1|H|3|I|5|6|7|X|8|@]|9|@]|C|$]]|$1|J|3|-4|5|6|7|Y|8|@]|9|@]|C|$]]]|K|$L|$5|M|N|O|C|$P|Q]]]]

That's the <a href="http://en.wikipedia.org/wiki/Hamming_weight">Hamming weight</a> problem, a.k.a. population count. The link mentions efficient implementations. Quoting:

<blockquote>
 With unlimited memory, we could simply create a large lookup table of the Hamming weight of every 64 bit integer
</blockquote>

blocks|key|4241051|text|我有一个计算O(Number+of+1's)时间的解决方案：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|4241052|bitcount(n):
++++count+=+0
++++while+n+>+0:
++++++++count+=+count+%2B+1
++++++++n+=+n+&+(n-1)
++++return+count|code-block|syntax|javascript|4241053|在最坏的情况下(当数字是2%5En+-+1，所有的1都是二进制)，它将检查每一位。|4241054|编辑:刚刚发现了一个非常好的恒定时间，恒定内存的位数算法。下面是用C编写的代码：|4241055|int+BitCount(unsigned+int+u)
{
+++++unsigned+int+uCount;

+++++uCount+=+u+-+((u+>>+1)+&+033333333333)+-+((u+>>+2)+&+011111111111);
+++++return+((uCount+%2B+(uCount+>>+3))+&+030707070707)+%25+63;
}|4241056|你可以在here上找到它的正确性证明。|4241057|entityMap|0|LINK|mutability|MUTABLE|url|https://web.archive.org/web/20151229003112/http://blogs.msdn.com/b/jeuge/archive/2005/06/08/hakmem-bit-count.aspx^0|6|G|0|0|0|0|0|4|4|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@$9|11|A|12|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|13|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|14|8|@]|D|@]|E|$]]|$1|M|3|N|5|6|7|15|8|@]|D|@]|E|$]]|$1|O|3|P|5|H|7|16|8|@]|D|@]|E|$I|J]]|$1|Q|3|R|5|6|7|17|8|@]|D|@$9|18|A|19|1|1A]]|E|$]]|$1|S|3|-4|5|6|7|1B|8|@]|D|@]|E|$]]]|T|$U|$5|V|W|X|E|$Y|Z]]]]

I've got a solution that counts the bits in <code>O(Number of 1's)</code> time:
<pre><code>bitcount(n):
 count = 0
 while n &gt; 0:
 count = count + 1
 n = n &amp; (n-1)
 return count
</code></pre>
In worst case (when the number is 2^n - 1, all 1's in binary) it will check every bit.
Edit:
Just found a very nice constant-time, constant memory algorithm for bitcount. Here it is, written in C:
<pre><code>int BitCount(unsigned int u)
{
 unsigned int uCount;

 uCount = u - ((u &gt;&gt; 1) &amp; 033333333333) - ((u &gt;&gt; 2) &amp; 011111111111);
 return ((uCount + (uCount &gt;&gt; 3)) &amp; 030707070707) % 63;
}
</code></pre>
You can find proof of its correctness <a href="https://web.archive.org/web/20151229003112/http://blogs.msdn.com/b/jeuge/archive/2005/06/08/hakmem-bit-count.aspx" rel="noreferrer">here</a>.

blocks|key|332246|text|请注意:+n&(n-+1+)总是消除最低有效的1。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|332247|因此，我们可以编写如下代码来计算1的数量：|332248|count=0;
while(n!=0){
++n+=+n&(n-1);
++count%2B%2B;
}
cout<<"Number+of+1's+in+n+is:+"<<count;|code-block|syntax|javascript|332249|程序的复杂度是:n中1的个数(始终小于32)。|332250|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|O|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Please note the fact that: n&amp;(n-1) always eliminates the least significant 1. 

Hence we can write the code for calculating the number of 1's as follows:

<pre><code>count=0;
while(n!=0){
 n = n&amp;(n-1);
 count++;
}
cout&lt;&lt;"Number of 1's in n is: "&lt;&lt;count;
</code></pre>

The complexity of the program would be: number of 1's in n (which is constantly &lt; 32).

blocks|key|332931|text|我在另一个网站上看到了下面的解决方案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|332932|int+count_one(int+x){
++++x+=+(x+&+(0x55555555))+%2B+((x+>>+1)+&+(0x55555555));
++++x+=+(x+&+(0x33333333))+%2B+((x+>>+2)+&+(0x33333333));
++++x+=+(x+&+(0x0f0f0f0f))+%2B+((x+>>+4)+&+(0x0f0f0f0f));
++++x+=+(x+&+(0x00ff00ff))+%2B+((x+>>+8)+&+(0x00ff00ff));
++++x+=+(x+&+(0x0000ffff))+%2B+((x+>>+16)+&+(0x0000ffff));
++++return+x;
}|code-block|syntax|javascript|332933|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

I saw the following solution from another website:

<pre><code>int count_one(int x){
 x = (x &amp; (0x55555555)) + ((x &gt;&gt; 1) &amp; (0x55555555));
 x = (x &amp; (0x33333333)) + ((x &gt;&gt; 2) &amp; (0x33333333));
 x = (x &amp; (0x0f0f0f0f)) + ((x &gt;&gt; 4) &amp; (0x0f0f0f0f));
 x = (x &amp; (0x00ff00ff)) + ((x &gt;&gt; 8) &amp; (0x00ff00ff));
 x = (x &amp; (0x0000ffff)) + ((x &gt;&gt; 16) &amp; (0x0000ffff));
 return x;
}
</code></pre>

blocks|key|4241174|text|public+static+void+main(String[]+args)+{

++++int+a+=+3;
++++int+orig+=+a;
++++int+count+=+0;
++++while(a>0)
++++{
++++++++a+=+a+>>+1+<<+1;
++++++++if(orig-a==1)
++++++++++++count%2B%2B;
++++++++orig+=+a+>>+1;
++++++++a+=+orig;
++++}

++++System.out.println("Number+of+1s+are:+"%2Bcount);
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|4241175|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>public static void main(String[] args) {

 int a = 3;
 int orig = a;
 int count = 0;
 while(a&gt;0)
 {
 a = a &gt;&gt; 1 &lt;&lt; 1;
 if(orig-a==1)
 count++;
 orig = a &gt;&gt; 1;
 a = orig;
 }

 System.out.println("Number of 1s are: "+count);
}
</code></pre>

blocks|key|4241432|text|+++countBits(x){
+++++y=0;
+++++while(x){+++
+++++++y+%2B=+x+&++1+;
+++++++x++=+x+>>+1+;
+++++}
+++}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|4241433|就这样吗？|unstyled|4241434|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|J|8|@]|9|@]|A|$]]|$1|G|3|-4|5|F|7|K|8|@]|9|@]|A|$]]]|H|$]]

<pre><code> countBits(x){
 y=0;
 while(x){ 
 y += x &amp; 1 ;
 x = x &gt;&gt; 1 ;
 }
 }
</code></pre>

thats it?

blocks|key|200072|text|这将是我一生中最简短的答案：查找表。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|200073|显然，我需要解释一下：“如果你有足够的内存玩”，意思是，我们已经有了我们需要的所有内存(别管技术上的可能性)。现在，您不需要存储超过一两个字节的查找表。虽然从技术上讲，它将是对数(Ω(N))而不是O(1)，但仅仅读取您需要的数字就是对数(Ω(N))，所以如果这是一个问题，那么答案是，log更短。|200074|没有人知道他们在面试时会从你那里得到哪一个答案。|200075|还有另一个诀窍:虽然工程师可以取一个数字并谈论对数(Ω(N))，其中n是数字，但计算机科学家会说，实际上我们是作为输入长度的函数来测量运行时间的，所以工程师所说的Ω(Ω(N))实际上是Ω(k)，其中k是字节数。尽管如此，正如我之前所说的，仅仅读取一个数字就是Ω(k)，所以我们没有办法比这个做得更好。|200076|entityMap^0|E|4|0|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@$9|O|A|P|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Q|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|R|8|@]|D|@]|E|$]]|$1|J|3|K|5|6|7|S|8|@]|D|@]|E|$]]|$1|L|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|M|$]]

That will be the shortest answer in my SO life: lookup table.

Apparently, I need to explain a bit: "if you have enough memory to play with" means, we've got all the memory we need (nevermind technical possibility). Now, you don't need to store lookup table for more than a byte or two. While it'll technically be Ω(log(n)) rather than O(1), just reading a number you need is Ω(log(n)), so if that's a problem, then the answer is, impossible—which is even shorter.

Which of two answers they expect from you on an interview, no one knows.

There's yet another trick: while engineers can take a number and talk about Ω(log(n)), where n is the number, computer scientists will say that actually we're to measure running time as a function of a length of an input, so what engineers call Ω(log(n)) is actually Ω(k), where k is the number of bytes. Still, as I said before, just reading a number is Ω(k), so there's no way we can do better than that.

blocks|key|4241523|text|下面是两个简单的示例(用C%2B%2B编写)，您可以通过它们来实现这一点。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4241524|4241525|我们可以使用__builtin_popcount()简单地计算设置位(1)。|ordered-list-item|4241526|4241527|对整数中的所有位进行计数，检查是否设置了某一位，如果设置了，则递增int+numOfOnes(int+x)+{+++++++++return+__builtin_popcount(x);+++++}|offset|length|style|CODE|4241528|Loop变量。|unordered-list-item|4241529|4241530|int+hammingDistance(int+x)+{+++++++++int+count+=+0+++++++++for(int+i+=+0;+i+<+32;+i%2B%2B)+++++++++++++if(x+&+(1+<<+i))+count%2B%2B;+++++++++return+count;+++++}|4241531|希望这能有所帮助！|4241532|entityMap^0|0|0|0|0|X|1U|0|0|0|0|48|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|X|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|Y|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|10|8|@$I|11|J|12|K|L]]|9|@]|A|$]]|$1|M|3|N|5|O|7|13|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|14|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|15|8|@$I|16|J|17|K|L]]|9|@]|A|$]]|$1|S|3|T|5|6|7|18|8|@]|9|@]|A|$]]|$1|U|3|-4|5|6|7|19|8|@]|9|@]|A|$]]]|V|$]]

Below are two simple examples (in C++) among many by which you can do this. 

<ol>
<li>We can simply count set bits (1's) using __builtin_popcount().

<code>int numOfOnes(int x) {
 return __builtin_popcount(x);
 }</code></li>
<li>Loop through all bits in an integer, check if a bit is set and if it is then increment the count variable.

<code>int hammingDistance(int x) {
 int count = 0
 for(int i = 0; i &lt; 32; i++)
 if(x &amp; (1 &lt;&lt; i)) count++;
 return count;
 }</code></li>
</ol>

Hope this helps!

blocks|key|332946|text|下面的代码也同样适用。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|332947|nofone(int+x)+{
++a=0;
++while(x!=0)+{
++++x>>=1;
++++if(x+&+1)
++++++a%2B%2B;
++}
++return+a;
}+|code-block|syntax|javascript|332948|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Below will work as well.

<pre><code>nofone(int x) {
 a=0;
 while(x!=0) {
 x&gt;&gt;=1;
 if(x &amp; 1)
 a++;
 }
 return a;
} 
</code></pre>

blocks|key|332280|text|下面是一个使用位运算符的C语言解决方案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|332281|int+numberOfOneBitsInInteger(int+input)+{
++int+numOneBits+=+0;

++int+currNum+=+input;
++while+(currNum+!=+0)+{
++++if+((currNum+&+1)+==+1)+{
++++++numOneBits%2B%2B;
++++}
++++currNum+=+currNum+>>+1;
++}
++return+numOneBits;
}|code-block|syntax|javascript|332282|下面是一个使用2的幂的Java解决方案：|332283|public+static+int+numOnesInBinary(int+n)+{

++if+(n+<+0)+return+-1;

++int+j+=+0;
++while+(+n+>+Math.pow(2,+j))+j%2B%2B;

++int+result+=+0;
++for+(int+i=j;+i+>=0;+i--){
++++if+(n+>=+Math.pow(2,+i))+{
++++++++n+=+(int)+(n+-+Math.pow(2,i));
++++++++result%2B%2B;++++
++++}
++}

++return+result;
}|332284|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

The following is a C solution using bit operators:

<pre><code>int numberOfOneBitsInInteger(int input) {
 int numOneBits = 0;

 int currNum = input;
 while (currNum != 0) {
 if ((currNum &amp; 1) == 1) {
 numOneBits++;
 }
 currNum = currNum &gt;&gt; 1;
 }
 return numOneBits;
}
</code></pre>

The following is a Java solution using powers of 2:

<pre><code>public static int numOnesInBinary(int n) {

 if (n &lt; 0) return -1;

 int j = 0;
 while ( n &gt; Math.pow(2, j)) j++;

 int result = 0;
 for (int i=j; i &gt;=0; i--){
 if (n &gt;= Math.pow(2, i)) {
 n = (int) (n - Math.pow(2,i));
 result++; 
 }
 }

 return result;
}
</code></pre>

blocks|key|4241194|text|该函数接受一个int，并以二进制形式返回1的个数|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|4241195|public+static+int+findOnes(int+number)
{

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

++++value+=+number+%25+2;

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

++++number+/=+2;

++++findOnes(number);

++++return+count;
}|code-block|syntax|javascript|4241196|entityMap^0|7|3|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@$9|N|A|O|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|P|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|D|@]|E|$]]]|L|$]]

The function takes an <code>int</code> and returns the number of Ones in binary representation

<pre><code>public static int findOnes(int number)
{

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

 value = number % 2;

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

 number /= 2;

 findOnes(number);

 return count;
}
</code></pre>

blocks|key|1353466|text|在javascript中这样做的最好方法是|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1353467|function+getBinaryValue(num){
+return+num.toString(2);
}

function+checkOnces(binaryValue){
++++return+binaryValue.toString().replace(/0/g,+"").length;
}|code-block|syntax|javascript|1353468|其中binaryValue是二进制字符串，例如:+1100|1353469|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

The best way in javascript to do so is

<pre><code>function getBinaryValue(num){
 return num.toString(2);
}

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

where binaryValue is the binary String eg: 1100

blocks|key|200260|text|在O(1)中，我只能想到一种方法来完成这个任务……也就是说，“作弊”并使用物理设备(对于线性甚至并行编程，我认为限制是O(log(k))，其中k表示该数字的字节数)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|200261|然而，您可以很容易地想象一个物理设备，它以0/1电压将每个位连接到输出线。然后你就可以通过电子方式读取O(1)中“求和”线上的总电压。用一些基本的电路元件来产生你想要的任何形式的输出(例如二进制编码的输出)来使这个基本思想更加优雅是相当容易的，但基本思想是相同的，并且电子电路将在固定的时间内产生正确的输出状态。|200262|我想也有可能有量子计算的可能性，但如果我们被允许这样做，我会认为一个简单的电子电路是更容易的解决方案。|200263|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

There's only one way I can think of to accomplish this task in O(1)... that is to 'cheat' and use a physical device (with linear or even parallel programming I think the limit is O(log(k)) where k represents the number of bytes of the number).

However you could very easily imagine a physical device that connects each bit an to output line with a 0/1 voltage. Then you could just electronically read of the total voltage on a 'summation' line in O(1). It would be quite easy to make this basic idea more elegant with some basic circuit elements to produce the output in whatever form you want (e.g. a binary encoded output), but the essential idea is the same and the electronic circuit would produce the correct output state in fixed time.

I imagine there are also possible quantum computing possibilities, but if we're allowed to do that, I would think a simple electronic circuit is the easier solution.

blocks|key|4241160|text|我实际上使用了一些技巧来完成这一点:一个包含16个条目的单一查找表就足够了，您所要做的就是将二进制表示分解为四位字节(4位元组)。复杂度实际上是O(1)，我编写了一个专门针对您想要的整数(以#…为单位)大小的C%2B%2B模板使其成为常量表达式，而不是不确定的表达式。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4241161|fwiw你可以利用(i+&+-i)将返回LS一位的事实，并简单地循环，每次剥离lsbit，直到整数为零-但这是一个古老的奇偶校验技巧。|4241162|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

I have actually done this using a bit of sleight of hand: a single lookup table with 16 entries will suffice and all you have to do is break the binary rep into nibbles (4-bit tuples). The complexity is in fact O(1) and I wrote a C++ template which was specialized on the size of the integer you wanted (in # bits)… makes it a constant expression instead of indetermined.

fwiw you can use the fact that (i &amp; -i) will return you the LS one-bit and simply loop, stripping off the lsbit each time, until the integer is zero — but that’s an old parity trick.

blocks|key|4241337|text|我来到这里，怀着一个伟大的信念，我知道这个问题的完美解决方案。用C编写的代码：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4241338|++++short+numberOfOnes(unsigned+int+d)+{
++++++++short+count+=+0;

++++++++for+(;+(d+!=+0);+d+&=+(d+-+1))
++++++++++++%2B%2Bcount;

++++++++return+count;
++++}|code-block|syntax|javascript|4241339|但在我对这个主题做了一些研究之后(阅读其他答案：)，我发现了5个更有效的算法。我爱死你了！|4241340|甚至还有专门为此任务设计的CPU指令：popcnt。(在this+answer中提到)|offset|length|style|CODE|4241341|许多算法的描述和基准测试，你可以找到here。|4241342|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/14682688/1429387|1|http://gurmeet.net/puzzles/fast-bit-counting-routines^0|0|0|0|J|6|S|B|0|0|I|4|1|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|11|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|12|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|13|8|@$K|14|L|15|M|N]]|9|@$K|16|L|17|1|18]]|A|$]]|$1|O|3|P|5|6|7|19|8|@]|9|@$K|1A|L|1B|1|1C]]|A|$]]|$1|Q|3|-4|5|6|7|1D|8|@]|9|@]|A|$]]]|R|$S|$5|T|U|V|A|$W|X]]|Y|$5|T|U|V|A|$W|Z]]]]

I came here having a great belief that I know beautiful solution for this problem. Code in C:

<pre><code> short numberOfOnes(unsigned int d) {
 short count = 0;

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

 return count;
 }
</code></pre>

But after I've taken a little research on this topic (read other answers:)) I found 5 more efficient algorithms. Love SO!

There is even a CPU instruction designed specifically for this task: <code>popcnt</code>.
(mentioned in <a href="https://stackoverflow.com/a/14682688/1429387">this answer</a>)

Description and benchmarking of many algorithms you can find <a href="http://gurmeet.net/puzzles/fast-bit-counting-routines" rel="nofollow noreferrer">here</a>.

blocks|key|333013|text|在python或其他任何地方，转换为bin字符串，然后用'0‘将其拆分，去掉0，然后组合并获得长度。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|333014|len(''.join(str(bin(122011)).split('0')))-1|code-block|syntax|javascript|333015|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

In python or any other convert to bin string then split it with '0' to get rid of 0's then combine and get the length.

<pre><code>len(''.join(str(bin(122011)).split('0')))-1
</code></pre>

blocks|key|333036|text|下面的方法也可以计算1的负数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|333037|private+static+int+countBits(int+number)++++{
++++int+result+=+0;
++++while(number+!=+0)++{
++++++++result+%2B=+number+&+1;
++++++++number+=+number+>>>+1;
++++}
++++return+result;
}|code-block|syntax|javascript|333038|但是，像-1这样的数字以二进制形式表示为111111111111111111111111111111111111111111111111111111，因此需要进行大量的移位。如果你不想对小的负数做这么多的移位，另一种方法可以如下所示：|333039|private+static+int+countBits(int+number)++++{
++++boolean+negFlag+=+false;
++++if(number+<+0)++{+
++++++++negFlag+=+true;
++++++++number+=+~number;
++++}

++++int+result+=+0;
++++while(number+!=+0)++{
++++++++result+%2B=+number+&+1;
++++++++number+=+number+>>+1;
++++}
++++return+negFlag?+(32-result):+result;
}|333040|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

The below method can count the number of 1s in negative numbers as well.

<pre><code>private static int countBits(int number) {
 int result = 0;
 while(number != 0) {
 result += number &amp; 1;
 number = number &gt;&gt;&gt; 1;
 }
 return result;
}
</code></pre>

However, a number like -1 is represented in binary as 11111111111111111111111111111111 and so will require a lot of shifting. If you don't want to do so many shifts for small negative numbers, another way could be as follows:

<pre><code>private static int countBits(int number) {
 boolean negFlag = false;
 if(number &lt; 0) { 
 negFlag = true;
 number = ~number;
 }

 int result = 0;
 while(number != 0) {
 result += number &amp; 1;
 number = number &gt;&gt; 1;
 }
 return negFlag? (32-result): result;
}
</code></pre>

blocks|key|200606|text|通过利用JS的字符串操作，可以执行以下操作；|type|unstyled|depth|inlineStyleRanges|entityRanges|data|200607|0b1111011.toString(2).split(/0%7C(?=.)/).length+//+returns+6|code-block|syntax|javascript|200608|或|200609|0b1111011.toString(2).replace("0","").length++//+returns+6|200610|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

By utilizing string operations of JS one can do as follows;

<pre><code>0b1111011.toString(2).split(/0|(?=.)/).length // returns 6
</code></pre>

or

<pre><code>0b1111011.toString(2).replace("0","").length // returns 6
</code></pre>

blocks|key|4241561|text|我不得不在红宝石上打高尔夫，最后得到了|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4241562|l=->x{x.to_s(2).count+?1}|code-block|syntax|javascript|4241563|用法：|4241564|l[2**32-1]+#+returns+32|offset|length|style|CODE|4241565|显然效率不高，但效果很好:)|4241566|entityMap^0|0|0|0|0|N|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|V|8|@$K|W|L|X|M|N]]|9|@]|A|$]]|$1|O|3|P|5|6|7|Y|8|@]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|R|$]]

I had to golf this in ruby and ended up with

<pre><code>l=-&gt;x{x.to_s(2).count ?1}
</code></pre>

Usage : 

<code>l[2**32-1] # returns 32</code>

Obviously not efficient but does the trick :)

blocks|key|332357|text|Ruby实现|type|unstyled|depth|inlineStyleRanges|entityRanges|data|332358|def+find_consecutive_1(n)
++num+=+n.to_s(2)
++arr+=+num.split("")
++counter+=+0
++max+=+0
++arr.each+do+%7Cx%7C
++++++if+x.to_i==1
++++++++++counter+%2B=1
++++++else
++++++++++max+=+counter+if+counter+>+max
++++++++++counter+=+0+
++++++end
++++++max+=+counter+if+counter+>+max++
++end
++max
end

puts+find_consecutive_1(439)|code-block|syntax|javascript|332359|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Ruby implementation 

<pre><code>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 &gt; max
 counter = 0 
 end
 max = counter if counter &gt; max 
 end
 max
end

puts find_consecutive_1(439)
</code></pre>

blocks|key|4241636|text|Two+ways::|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|4241637|/*+Method-1+*/
int+count1s(long+num)
{
++++int+tempCount+=+0;

++++while(num)
++++{
++++++++tempCount+%2B=+(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%2B%2B)
++++{
++++++++if('1'+==+strNum[i])
++++++++{
++++++++++++tempCount%2B%2B;
++++++++}
++++}

++++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|code-block|syntax|javascript|4241638|用法：：|4241639|++++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|4241640|entityMap^0|0|A|0|0|0|4|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@$9|R|A|S|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|T|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|U|8|@$9|V|A|W|B|C]]|D|@]|E|$]]|$1|M|3|N|5|H|7|X|8|@]|D|@]|E|$I|J]]|$1|O|3|-4|5|6|7|Y|8|@]|D|@]|E|$]]]|P|$]]

Two ways::

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

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

 return tempCount;
}

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

 std::string strNum = std::bitset&lt; 16 &gt;( num ).to_string(); // string conversion
 cout &lt;&lt; "strNum=" &lt;&lt; strNum &lt;&lt; endl;
 for(int i=0; i&lt;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
</code></pre>

Usage::

<pre><code> int count = 0;

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

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

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

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

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

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

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

 count = count1s_(0b1);
 cout &lt;&lt; "count(0b1) = " &lt;&lt; count &lt;&lt; endl; //1
</code></pre>

Efficient way to count number of 1s in the binary representation of a number in O(1) if you have enough memory to play with. This is an interview question I found on an online forum, but it had no answer. Can somebody suggest something, I cant think of a way to do it in O(1) time?

Count number of 1's in binary representation

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

如果你有足够的内存来计算O(1)中一个数的二进制表示中的1的个数，这是一个有效的方法。这是我在一个在线论坛上找到的一个面试问题，但它没有答案。有人能提个建议吗?我想不出能在O(1)时间内完成的方法。

问计数二进制表示的1的个数
EN

回答 21

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计数二进制表示的1的个数EN

回答 21

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计数二进制表示的1的个数
EN