Interview Question

Software Engineer Interview Olathe, KS

Write a function to count the number of bits that are set

  in an int.
Answer

Interview Answer

1 Answer

0

There are several ways to do this, here are two. Brian Kernighan’s Algorithm for Sparse shown below which is fast, simple, and the number of loops is equal to the number of set bits(1). Then there is the iterative way to do it below that.

int GetBitcountSparse(int someNumber)
{
    int bitsSet= 0;
    while (someNumber != 0)
    {
        bitsSet++;
        someNumber &= (someNumber - 1);
    }
    return bitsSet;
}

int GetBitcountIterated(int someNumber)
{
    int bitsSet= 0;

    while (test != 0)
    {
        if ((someNumber& 1) == 1)
            bitsSet++;

        someNumber>>= 1;
    }
    return bitsSet;
}

Note that either of these could be static method as they are stateless and were written with C# in mind.

Anonymous on Aug 2, 2012

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up