Count number of 1 s in binary representation

Question

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

User · Answer

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   count 0  while n  0     n   n amp  n-1     count      cout lt  lt  Number of 1 s in n is    lt  lt count    The complexity of the program would be  number of 1 s in n  which is constantly  lt  32

User · Answer

I saw the following solution from another website   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

User · Answer

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 O log n   rather than O 1   just reading a number you need is O 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 O 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 O log n   is actually O k   where k is the number of bytes  Still  as I said before  just reading a number is O k   so there s no way we can do better than that

User · Answer

I came here having a great belief that I know beautiful solution for this problem  Code in C       short numberOfOnes unsigned int d            short count   0           for     d    0   d  amp    d - 1                 count           return count          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  popcnt   mentioned in this answer   Description and benchmarking of many algorithms you can find here

User · Answer

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

User · Answer

Below are two simple examples  in C    among many by which you can do this     We can simply count set bits  1 s  using   builtin popcount     int numOfOnes int x            return   builtin popcount x         Loop through all bits in an integer  check if a bit is set and if it is then increment the count variable   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          Hope this helps

User · Answer

The below method can count the number of 1s in negative numbers as well   private static int countBits int number           int result   0      while number    0             result    number  amp  1          number   number  gt  gt  gt  1            return result      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   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

User · Answer

I ve got a solution that counts the bits in O Number of 1 s  time  bitcount n       count   0     while n  gt  0          count   count   1         n   n  amp   n-1      return count  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  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     You can find proof of its correctness here

User · Answer

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

User · Answer

Below will work as well   nofone int x      a 0    while x  0        x gt  gt  1      if x  amp  1        a          return a

User · Answer

The following is a C solution using bit operators   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      The following is a Java solution using powers of 2   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

User · Answer

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   len    join str bin 122011   split  0    -1

User · Answer

The function takes an int and returns the number of Ones in binary representation  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

User · Answer

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

User · Answer

By utilizing string operations of JS one can do as follows   0b1111011 toString 2  split  0         length    returns 6   or  0b1111011 toString 2  replace  0      length     returns 6

User · Answer

Two ways       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   Usage        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

User · Answer

I had to golf this in ruby and ended up with  l - gt x x to s 2  count  1    Usage     l 2  32-1    returns 32  Obviously not efficient but does the trick

User · Answer

The best way in javascript to do so is  function getBinaryValue num    return num toString 2      function checkOnces binaryValue       return binaryValue toString   replace  0 g      length      where binaryValue is the binary String eg  1100

User · Answer

Ruby implementation   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

User · Answer

That s the Hamming weight problem  a k a  population count  The link mentions efficient implementations  Quoting      With unlimited memory  we could simply create a large lookup table of the Hamming weight of every 64 bit integer

User · Answer

countBits x        y 0       while x             y    x  amp   1          x    x  gt  gt  1                 thats it

[algorithm] Count number of 1's in binary representation

Examples related to algorithm

Examples related to binary