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?

Answer 1

I use this helper class to calculate the number of 1s in a 64-bit long in C#. It stores 8-bits in precomputed table.

public static class BitUtils
{
    private static readonly byte[] _bitCountTable = new byte[256];

    static BitUtils()
    {
        for (int i = 0; i < 256; i++)
        {
            _bitCountTable[i] = (byte)GetBitCount(i);
        }
    }

    static int GetBitCount(int value)
    {
        int count = 0;
        while (value != 0)
        {
            count += value & 1;
            value >>= 1;
        }
        return count;
    }

    public static int PopCount(ulong value)
    {
        int count = 0;
        for (int i = 0; i < 8; i++)
        {
            count += _bitCountTable[(value >> (i * 8)) & 0xFF];
        }
        return count;
    }
}

I compared it with other ways like looping or using strings. Here are the performances:

• Looping - 50-60ns
• Strings - 1000ns
• Precomputed - 20-30ns

Answer 2

       countBits(x){
         y=0;
         while(x){   
           y += x &  1 ;
           x  = x >> 1 ;
         }
       }

thats it?

Answer 3

I had to golf this in ruby and ended up with

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

Usage :

l[2**32-1] # returns 32

Obviously not efficient but does the trick :)

Answer 4

The function takes an int and returns the number of Ones in binary representation

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;
}

Answer 5

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 > max
              counter = 0 
          end
          max = counter if counter > max  
      end
      max
    end

    puts find_consecutive_1(439)

Answer 6

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

Answer 7

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

Answer 8

I saw the following solution from another website:

    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;
    }

Answer 9

Please note the fact that: n&(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&(n-1);
  count++;
}
cout<<"Number of 1's in n is: "<<count;

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

Answer 10

The following is a C solution using bit operators:

    int numberOfOneBitsInInteger(int input) {
      int numOneBits = 0;

      int currNum = input;
      while (currNum != 0) {
        if ((currNum & 1) == 1) {
          numOneBits++;
        }
        currNum = currNum >> 1;
      }
      return numOneBits;
    }

The following is a Java solution using powers of 2:

    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;
    }

Answer 11

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 &= (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.

Answer 12

I've got a solution that counts the bits in O(Number of 1's) time:

bitcount(n):
    count = 0
    while n > 0:
        count = count + 1
        n = n & (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 >> 1) & 033333333333) - ((u >> 2) & 011111111111);
         return ((uCount + (uCount >> 3)) & 030707070707) % 63;
    }

You can find proof of its correctness here.

Answer 13

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);
}

Answer 14

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

1. We can simply count set bits (1's) using __builtin_popcount().

int numOfOnes(int x) {
  return __builtin_popcount(x);
}

2. 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 < 32; i++)
    if(x & (1 << i))
      count++;
  return count;
}

Answer 15

A Python one-liner

def countOnes(num):
    return bin(num).count('1')

Answer 16

Two ways::

/* 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

Usage::

    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

Answer 17

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

Answer 18

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 & 1;
        number = number >>> 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 < 0)  { 
        negFlag = true;
        number = ~number;
    }

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

Answer 19

Below will work as well.

nofone(int x) {
  a=0;
  while(x!=0) {
    x>>=1;
    if(x & 1)
      a++;
  }
  return a;
} 

Answer 20

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 & -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.

Answer 21

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.

Answer 22

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.

Answer 23

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