以二进制表示计算1的数目
如果你有足够的存储空间来处理O（1）中一个数字的二进制表示的有效方法。 这是我在网上论坛上find的面试问题，但是没有答案。 有人可以提出一些build议，我不能想办法在O（1）时间做到这一点吗？
这就是海明重量问题，也就是人口数量。 链接提到有效的实现。 引用：
使用无限的内存，我们可以简单地创build一个每64位整数的汉明权重的大查找表
我有一个解决scheme，计算O(Number of 1's)时间的位：
bitcount(n): count = 0 while n > 0: count = count + 1 n = n & (n-1) return count
在最坏的情况下（当数字是2 ^ n – 1，所有1都是二进制的）它将检查每一位。
编辑：刚刚发现一个非常好的恒定时间，记忆algorithmbitcount。 这里是用C写成的：
int BitCount(unsigned int u) { unsigned int uCount; uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111); return ((uCount + (uCount >> 3)) & 030707070707) % 63; }
你可以在这里find它的正确性certificate。
请注意事实：n＆（n-1）总是消除最不重要的1。
因此我们可以编写计算1的个数的代码如下：
count=0; while(n!=0){ n = n&(n-1); count++; } cout<<"Number of 1's in n is: "<<count;
该程序的复杂性将是：n的个数为1（不断<32）。
我从另一个网站上看到了以下解决scheme：
int count_one(int x){ x = (x & (0x55555555)) + ((x >> 1) & (0x55555555)); x = (x & (0x33333333)) + ((x >> 2) & (0x33333333)); x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f)); x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff)); x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff)); return x; }
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++; orig = a >> 1; a = orig; } System.out.println("Number of 1s are: "+count); }
countBits(x){ y=0; while(x){ y += x & 1 ; x = x >> 1 ; } }
而已？
这将是我SO生命中最短的回答： 查找表。
显然，我需要解释一下：“如果你有足够的内存来玩”的意思，我们已经得到了我们所需要的所有内存（从来不需要技术上的可能性）。 现在，您不需要将查找表存储超过一个或两个字节。 虽然在技术上它是Ω（log（n））而不是O（1），但是只需要读取一个你需要的数字就是Ω（log（n）），所以如果这是一个问题，那么答案是不可能的 ，甚至更短。
没有人知道他们在面试中期望得到的两个答案中的哪一个。
还有一个窍门：工程师可以拿一个数字并且讨论Ω（log（n）），其中n是数字，计算机科学家会说，实际上我们要测量运行时间作为input长度的函数，所以工程师叫Ω（log（n））实际上是Ω（k），其中k是字节数。 不过，正如我之前所说的，只读一个数字就是Ω（k），所以我们不可能做得比这更好。
下面也会工作。
nofone(int x) { a=0; while(x!=0) { x>>=1; if(x & 1) a++; } return a; }
该函数接受一个int并返回二进制表示的个数
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; }
以下是使用位运算符的C解决scheme：
int numberOfOneBitsInInteger(int input) { int numOneBits = 0; int currNum = input; while (currNum != 0) { if ((currNum & 1) == 1) { numOneBits++; } currNum = currNum >> 1; } return numOneBits; }
以下是使用2的幂的Java解决scheme：
public static int numOnesInBinary(int n) { if (n < 0) return -1; int j = 0; while ( n > Math.pow(2, j)) j++; int result = 0; for (int i=j; i >=0; i--){ if (n >= Math.pow(2, i)) { n = (int) (n - Math.pow(2,i)); result++; } } return result; }
在O（1）中只有一个办法可以完成这个任务…即“欺骗”并使用物理设备（使用线性甚至并行编程，我认为极限是O（log（k））其中k代表号码的字节数）。
然而，你可以很容易地想象一个物理设备，连接每一位和0/1电压输出线。 然后你可以用电子方法读取O（1）中“求和”的总电压。 用一些基本的电路元件来使这个基本思想更加优雅，以产生你想要的任何forms的输出（例如二进制编码输出），但是基本思想是相同的，电子电路将产生正确的输出固定时间的状态。
我想也有可能的量子计算的可能性，但如果我们被允许这样做，我会认为一个简单的电子电路是更容易的解决scheme。
实际上，我已经使用了一些技巧来做到这一点：只需要一个包含16个条目的查找表就足够了，而您所要做的就是将二进制代码分解为四位元组（bit）。 实际上复杂性是O（1），我写了一个C ++模板，它专门针对你想要的整数大小（以＃位为单位）…使它成为一个常量expression式，而不是无限的。
你可以使用这样一个事实，即（i和-i）会返回你的LS一位，并简单地循环，每次剥离lsbit，直到整数为零 – 但这是一个旧的奇偶技巧。
我来到这里有一个伟大的信念，我知道这个问题的美丽的解决scheme。 代码C：
short numberOfOnes(unsigned int d) { short count = 0; for (; (d != 0); d &= (d - 1)) ++count; return count; }
但是，在我对这个主题进行了一些研究（阅读其他答案:)）后，我发现了5个更有效的algorithm。 爱这样！
甚至还有专门为此任务devise的CPU指令： popcnt 。 （在这个答案中提到）
许多algorithm的描述和基准testing可以在这里find。
下面的方法也可以计算负数中的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; }
在Python或任何其他转换为二进制string，然后拆分它与'0'摆脱0的，然后结合起来，并获得长度。
len(''.join(str(bin(122011)).split('0')))-1
利用JS的string操作可以做到以下几点：
0b1111011.toString(2).split(/0|(?=.)/).length // returns 6
要么
0b1111011.toString(2).replace("0","").length // returns 6
下面是两个简单的例子（在C ++中），你可以做到这一点。
-
我们可以简单地使用__builtin_popcount（）来计算设置位（1）。
int numOfOnes(int x) { return __builtin_popcount(x); } -
遍历整数中的所有位，检查是否设置了一位，如果是，则递增计数variables。
int hammingDistance(int x) { int count = 0 for(int i = 0; i < 32; i++) if(x & (1 << i)) count++; return count; }
希望这可以帮助！
我不得不用ruby打高尔夫球，并以此结束
l=->x{x.to_s(2).count ?1}
用法：
l[2**32-1] # returns 32
显然不高效，但诀窍:)
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)
两种方式::
/* 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
