algortihm optmization

[I_m_rude]

Can anyone tell me the best way to check the number of bits in a number ? for ex, in 2 set bits are1 , in 3 it is 2. So what is best way today available so as to get that value ? thanks. just give me link of algo, i wana code it myself. Give me hint or algo's link. thanks in advance.

[deceptikon]

"Best" is subjective and dependent on the needs of the situation, but a concise and reasonable generic solution is this one:

int count_set_bits(int value)
{
    int n = 0;

    while (value) {
        value &= value - 1;
        ++n;
    }

    return n;
}

The benefit of this algorithm over the more naive loop is that this one only iterates as many times as there are set bits. The naive loop would loop as many times as there are bits in the type and include an extra test for a set bit:

int count_set_bits(int value)
{
    int n = 0;
    size_t i;

    for (i = 0; i < sizeof value * CHAR_BIT; ++i) {
        if (value & 1)
            ++n;

        value >>= 1;
    }

    return n;
}

Further options make increasingly more assumptions about the machine, but they can be very quick relative to the loop options because there aren't any conditionals or jumps.

This is a page you might find informative for bit magic.

[I_m_rude]

how do you come to know about these types of links which you have given above ? ^.^ thanks in advance to james sir. ;)

[deceptikon]

how do you come to know about these types of links which you have given above ?

Programming is my hobby as well as my job, so I do a lot of reading on the subject. It should go without saying that I'll encounter interesting texts and web pages every now and again. ;)

[I_m_rude]

:'( hmm.. in other words, You are genius. haven't you done codechef, spoj like online judges in your school or university time ?

[deceptikon]

in other words, You are genius.

Absolutely not. I make up for lack of talent and average intelligence with heaps of effort.

haven't you done codechef, spoj like online judges in your school or university time ?

I'm not a fan of code competitions. Not only are the takeaway skills largely useless as a professional programmer, they highlight my complete lack of ability to devise clever and obtuse solutions that fit within the draconian performance and space requirements. ;)

[I_m_rude]

sorry, i didn't get. You saying that codechef like things is not neccessary for a professional programmer ? If yes, then will you please tell why is it so ?

[deceptikon]

If yes, then will you please tell why is it so ?

The tricks one uses to win a contest are nifty, but would fail any code review for production quality software. It's just like the tricks used in the IOCCC, they're only useful for the contest.

[I_m_rude]

hmm... One TRICKY sentence i wana say you on this thing ;) "Magicians never tell tricks of their magics ;)". I know what you are, Still you saying you are not genius blah blah. :-D

[neeratyoy.mallik]

int noOfBits(int n)
{
    int a=0;
    while(n>0)
    {
              if(n&1)
                     a++;
              n=n>>1;
     }
     return a;
}

this worked for me

[I_m_rude]

brute force... decptikon gives the best. ;) he is solution of my every problem of programming.. ;) thanks