Number of samples 1 in binary representation

Question

An efficient way to count the number 1 in the binary representation of a number in O (1), if you have enough memory to play. This is a question from an interview I found on an online forum, but it did not have an answer. Can someone suggest something, I can’t think of a way to do it O (1) times?

Answer 1

What is Hamming's problem, aka population The link mentions effective implementations. Citation:

With unlimited memory, we could simply create a large Hamming weight lookup table for each 64-bit integer

Answer 2

I have a solution that counts a bit in O(Number of 1's) time:

 bitcount(n): count = 0 while n > 0: count = count + 1 n = n & (n-1) return count 

In the worst case (when the number is 2 ^ n - 1, all 1 is binary), it will check every bit.

Edit: Just found a very nice persistent read-only 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 confirmation of its correctness here .

Answer 3

Note that: n & (n-1) always excludes the least significant 1.

Therefore, we can write code to calculate the number 1 as follows:

 count=0; while(n!=0){ n = n&(n-1); count++; } cout<<"Number of 1 in n is: "<<count; 

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

Answer 4

I saw the following solution from another site:

 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 5

 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 6

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

what is it?

Answer 7

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

Apparently, I need to clarify a little: "if you have enough memory for the game," then we have all the memory we need (technical ability is unimportant). Now you do not need to store the lookup table for more than a byte or two. Although it will technically be Ω (log (n)) and not O (1), just reading the number you need is Ω (log (n)), so if this is a problem then the answer will be impossible , which is even shorter .

Which of the two answers they expect from you at the interview, no one knows.

There’s another trick: while engineers can take a number and talk about Ω (log (n)), where n is a number, computer scientists will say that we actually have to measure the runtime as a function of input length, so engineers call Ω (log (n)) actually Ω (k), where k is the number of bytes. However, as I said, just reading the number is equal to Ω (k), so we cannot do it better.

Answer 8

Below will also work.

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

Answer 9

The function accepts int and returns the number of units 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 10

The following is a C solution using bitwise 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 authority 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

There is only one way that I can come up with this task in O (1) ... to “trick” 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 can easily imagine a physical device that connects each bit a to an output string with a voltage of 0/1. Then you can simply read the electronic message about the total voltage on the “summation” line in O (1). It would be quite easy to make this basic idea more elegant with some basic circuit elements for outputting output in any form (for example, binary encoded output), but the basic idea is the same and the electronic circuit will create the correct output state at a fixed time.

I suppose that the possibilities of quantum computing are also possible, but if we are allowed to do this, I think that a simple electronic circuit is an easier solution.

Answer 12

I actually did this using a bit of sleight of hand: just one lookup table with 16 entries is enough, and all you have to do is split the binary rep into nibbles (4-bit tuples). The complexity is actually O (1), and I wrote a C ++ pattern that was specialized in the size of the integer you wanted (in # bits) ... makes it a constant expression, not an undefined one.

fwiw you can use the fact that (i and -i) will return LS a single-bit and simple loop to you, each time canceling lsbit, until the integer becomes zero, but this is an old parity trick.

Answer 13

I came here with great conviction that I know a great solution to 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 researched this topic a bit (read other answers :)), I found 5 more efficient algorithms. Love SO!

There is even a CPU team specifically designed for this task: popcnt . (mentioned in this answer )

Description and comparative analysis of many algorithms can be found here .

Answer 14

In python or whatever, convert to a bin string, then divide it by “0” to get rid of 0, then combine and get the length.

 len(''.join(str(bin(122011)).split('0')))-1 

Answer 15

In the method below, you can also calculate the number 1s in negative numbers.

 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 1111111111111111111111111111111111, and therefore a lot of shift will be required. If you do not want to make so many shifts for small negative numbers, another way could be this:

 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 16

Using JS string operations, you can do the following:

 0b1111011.toString(2).split(/0|(?=.)/).length // returns 6 

or

 0b1111011.toString(2).replace("0","").length // returns 6 

Answer 17

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

• We can just count the bits of set (1) with __builtin_popcount ().

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

• Scroll all the bits to an integer, check if the bit is set, and if it then increments the counting 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!

Answer 18

I had to play golf in a ruby ​​and in the end

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

Using:

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

Obviously, it is not effective, but it does the trick :)

Answer 19

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 20

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 

Using::

  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