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

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?

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

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.

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

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

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.

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

thats it?

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

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 :)

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

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

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.

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

Below will work as well.

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

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)

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.

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.

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

Hope this helps!

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

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

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