Check if the binary of a number has equal no of 0's and 1's [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

We are given a integer number, and the task is to tell whether the binary representation of the number includes equal number of binary 1's and 0's or not?
I want the solution in constant time. I have the code for calculating no of 1s with the help of hamming weight algorithm!
Please help i want to count no of 0's!!

Answer 1

If x - is your number, N1 is the number of "1" then

int N0 = ceil(log2(x)) - N1;

will calculate number of "0". Do not forget

#include <math.h>

Answer 2

In production code (I mean if not restricted by rules dictated in an assignment) I'd do it like this:

#include <iostream>
#include <bitset>

int main()
{
    int k(24); // an example integer - the one you check for equality of 0's and ones
    std::bitset<32> bs(k); // I suppose 32 bit numbers - choose your own length

    if ( 16 == bs.count() ) // 16 is half the bit length - count returns the bits that are swithced ON
    {
        std::cout << "Equal number of 1s and 0s\n";
    }
}

I mean after all the question is tagged c++

Answer 3

int numberOfZeros = numberOfBinaryDigits - numberOfOnes;

Where number of binary digits is either based on the storage used for the data, or log2.

Answer 4

32 bit integer examples:

Using bit operators (and multiply):

int bitcount(unsigned int i)
{
    // generate a bit count in each pair of bits
    i = i - ( (i >> 1) & 0x55555555);
    // generate a bit count in each nibble
    i = (i & 0x33333333) + ( (i >> 2) & 0x33333333 );
    // sum up the bits counts in the nibbles
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

Using gcc popcount:

int bitcount(unsigned int i)
{
    return(__builtin_popcount(i));
}

using visual studio popcnt:

int bitcount(unsigned int i)
{
    return(_popcnt(i));
}

// if(16 == bitcount(i)), then equal number of 1's and 0's.