Puzzle: Count the number of 1-bits in an integer

Just posting this as a challenge for the code junkies out there. This is also a very common interview question for software jobs.

Q: Write a function to count the number of 1-bits in an unsigned integer. For example the integer 6 has a bitwise representation of 110, and thus contains two 1-bits.

Function prototype: int bitcount (unsigned int n); //A function call bitcount(6) should thus return 2

Once you come up with your initial working solution, the interviewer will keep asking you if you can make your algorithm faster and more efficient. Some ridiculously efficient solutions can be found here. Do give the question a serious attempt before you look at the solutions!

I would do it on compile time like this(for 16 bits only)

template

struct BitCount

{

enum {

bit15=(N & 32768) ? 1 : 0,

bit14=(N & 16384) ? 1 : 0,

bit13=(N & 8192) ? 1 : 0,

bit12=(N & 4096) ? 1 : 0,

bit11=(N & 2048) ? 1 : 0,

bit10=(N & 1024) ? 1 : 0,

bit9=(N & 512) ? 1 : 0,

bit8=(N & 256) ? 1 : 0,

bit7=(N & 128) ? 1 : 0,

bit6=(N & 64) ? 1 : 0,

bit5=(N & 32) ? 1 : 0,

bit4=(N & 16) ? 1 : 0,

bit3=(N & 8) ? 1 : 0,

bit2=(N & 4) ? 1 : 0,

bit1=(N & 2) ? 1 : 0,

bit0=(N & 1) ? 1 : 0

};

public:

enum{SetBits=bit15+bit14+bit13+bit12+bit11+bit10+bit9+bit8+bit7+bit6+bit5+bit4+bit3+bit2+bit1+bit0};

};

to use it

BitCount<6>::SetBits;

btw i am not a code junky whatever that means.

^ A code junky is a person who can't stay away from coding and if he/she does, goes into withdrawal! :P

First of all, thanks for coming up with your solution and replying. In my experience here at WiredPakistan, you might find amazing web developers, but very few people who are genuinely passionate about compiled languages and embedded or systems level programming (as you can see you are the only one to post a reply!).

Now since we're all here to learn and exchange ideas, you will forgive me as I proceed to rip your solution apart :) :

1. Not quite answered the question: You were expected to use the function prototype provided. However that is minor and can be overlooked. The more important issue is that your code only caters to 16-bit integers. All modern day operating systems use 32-bit int's (http://www.viva64.com/terminology/Data_model.html) and hence this solution would fail miserably if it were given a large enough number.

2. Incorrect use of templates: Ummm...templates?...huh?!?! Why would you use a template for your struct? A template is used to allow your code to dynamically handle different data types. The question specifies that the type is an 'unsigned int', so there was absolutely no need to use templates. Also, you hard-coded the type into the template definition anyways (template ) thus rendering it completely useless!

3. Incorrect use of enum: I have no idea why you used enum's. An enum is used when you want to define a set of related constant integers. Your code arguably does not really need the bit variables to be constant, and although that part might be overlooked, using an enum for SetBits is just plain awkward!

4. Questionable OO Design: One of the primary themes of object oriented programming is encapsulation of data. This way the functionality is hidden and data which should not be exposed is rendered inaccessible. By using public data in your struct, not only can the user access SetBits, he can also directly access your first enum containing bit0 - bit15 (note that structs are public by default). Since your aim was to design a module which takes in an int and gives you back the number of 1-bits, using a struct for the purpose is completely inappropriate. You should either have used a function as the question originally asked, or at the very least should have made bit0 - bit15 private !

5. Highly inefficient: The ultimate aim is to produce an amazingly efficient solution since coming up with a correct solution is rather trivial. Your solution is not very efficient in terms of run-time, and terribly inefficient in terms of memory usage. You used 17 int's inside your struct (thats 17 * 4 = 68 bytes), when you could have written it using only 1 char (so thats 1 byte)!

Please do reply to my comments and if you disagree with anything then I eagerly await your 'rebuttal'!

>>Now since we're all here to learn and exchange ideas, you will forgive me as I proceed to rip your solution apart

thanks for ripping apart my solution :)

>>Not quite answered the question: You were expected to use the function prototype provided. However that is minor and can be overlooked.

Agreed, but the way i want to implement it(on compile time) doesn't allow me to do that.

>>The more important issue is that your code only caters to 16-bit integers. All modern day computers use 32-bit int's (http://www.viva64.com/terminology/Data_model.html) and hence this solution would fail miserably if it were given a large enough number.

the implementation can easily be extended for 32 or even 64 bit although that would be a bit lengthy.

>>Ummm...templates?...huh?!?! Why would you use a template for your struct? A template is used to allow your code to dynamically handle different data types. The question specifies that the type is an 'unsigned int', so there was absolutely no need to use templates. Also, you hard-coded the type into the template definition anyways (template ) thus rendering it completely useless!

My implementation is like a policy based class, I want to use templates because instantiation occurs at compile time and i want my program to be interpreted at compile time.

>>Incorrect use of enum: I have no idea why you used enum's. An enum is used when you want to define a set of related constant integers. Your code arguably does not really need the bit variables to be constant, and although that part might be overlooked, using an enum for SetBits is just plain awkward!

I could have used "static const int" instead of enum but i still have old habit of using enums this is called enum hack and is used for old compilers

>>Questionable OO Design: One of the primary themes of object oriented programming is encapsulation of data. This way the functionality is hidden and data which should not be exposed is rendered inaccessible. By using public data in your struct, not only can the user access SetBits, he can also directly access your first enum containing bit0 - bit15 (note that structs are public by default). Since your aim was to design a module which takes in an int and gives you back the number of 1-bits, using a struct for the purpose is completely inappropriate. You should either have used a function as the question originally asked, or at the very least should have made bit0 - bit15 private !

To begin with i am not following OO here so i have no obligation to follow it's themes, this is like a policy base class as already written above however i do agree that bits0-bits15 should be private, struct are also used frequently in policy based classes

>>Highly inefficient: The ultimate aim is to produce an amazingly efficient solution since coming up with a correct solution is rather trivial. Your solution is not very efficient in terms of run-time, and terribly inefficient in terms of memory usage. You used 17 int's inside your struct (thats 17 * 4 = 68 bytes), when you could have written it using only 1 char (so thats 1 byte)!

hmmm did you check my program urself? my program does calculation at compile time there is no runtime calculation!

for this statement

int k=BitCount<6>::SetBits;

disassembly:

mov dword ptr [k],2

only a single mov.

^ Ahh I see what you did. I missed the part where you claimed it to be a compile-time solution and was thinking of it being repeatedly used after compilation. The idea here was to make it a run-time module (e.g. a function), so you can apply different algorithms to calculate the 1-bits most efficiently. Thats why when this question is asked, you're given the function prototype I mentioned in the first post.

Regardless, this solution is interesting too! I never thought of the possibility of making the calculation at compile time. Good stuff!

I would favor the iterative approach where bitwise comparison and shifting is done. There might be other more efficient implementations but I would favor this one. Simple to implement and easy to understand.

^ I agree with you regarding simplicity. If you look at some of the solutions towards the end (link: http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/), you need to sit and stare at them for a good while before you understand how they work! However, the idea is to come up with creative and efficient solutions. The 1-bit counter question is trivial, but the more efficient solutions can be applied to other larger and more complicated problems and it would make a noticeable performance difference.

I personally found the sparse/dense ones to be very interesting and appealing. Its simple enough to understand, yet fairly powerful at the same time. The crux of that solution is this line: n &= (n - 1)

It drops the right most 1-bit from n, so if n is 1100, after that line is executed, n would be 1000. A very nice bit manipulation trick!

@asad

Don't worry about it's efficiency as the value is calculated at compile time and hard coded by compiler in mov instruction

As far as other solutions are concerned the one with Builtin Instruction is probably the fastest for me as it is translated to single SSE4 instruction.

I can't think of a more optimized solution for an int than that, good going mate

@tal: On a slightly off-topic note, you said you're a software developer (I assume professionally), and it seems you work with C++ quite a bit. What is the scope of that kind of software development in Pakistan?

I understand that a lot of web developers, graphic designers and such, work free-lance in Pakistan, doing projects for clients abroad (e.g. US). But in my personal experience in the Canadian software industry, companies tend to keep the core project teams back at their headquarters. Only the 'trivial' projects are outsourced to third world countries. What is your opinion regarding this issue?

I was hunting in my old programs folders and just got succeeded finding with the following solution. Yes frankly I am not in C++ for more than 5 years. Never I got a reason to use these in my real life. Also listed at http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel . It's not as much simple as other iterative and and sparse/dense count but it's more efficient with exactly 12 operations.

unsigned int valin, temp;

cin >> valin;

temp = valin;

/* Three step operations. */

temp = temp - ((temp >> 1) & 0x55555555);

temp = (temp & 0x33333333) + ((temp >> 2) & 0x33333333);

c = ((temp + (temp >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

/* ******************** */

cout << c;

[quote=", post:, topic:"]
@tal: On a slightly off-topic note, you said you're a software developer (I assume professionally), and it seems you work with C++ quite a bit. What is the scope of that kind of software development in Pakistan?

I understand that a lot of web developers, graphic designers and such, work free-lance in Pakistan, doing projects for clients abroad (e.g. US). But in my personal experience in the Canadian software industry, companies tend to keep the core project teams back at their headquarters. Only the 'trivial' projects are outsourced to third world countries. What is your opinion regarding this issue?

[/quote]

If you allow me to put my opinion in this regard... then in my experience there are several firms working out there for some local and overseas clients but a programmer must have enough strength to work with them as they really require a tough man to do in C++ and obviously with the better programming knowledge and skills... Hiring and Firing is on going fact... Stays, who works good. Gets Fired, who's not surely for the job.

Most of the work includes automation.

About outsourcing to individual programmers (free-lancing), it always is to keep core on their own back. Mostly and usually the module or set(s) of modules are handed over to the programmers to work on it. Not only with System Programing but even in Web Development mostly the firms keep their cores to their own selves and allow the programmers to have limited portion of the project where specifically the programmer is supposed to work.

On other hand a lot of firms have their sub-offices in the countries like Pakistan. They do hire people on Full Time job at the offices. There the employees might have a broader access to the core systems/projects. Then no matter what they use to work with... C++, Java programming or the Web Development tasks. The actual thing is the "NEED" they give the employee the access what he/she actually needs to perform his/her job.... So there they keep them selves away from free-lancing the jobs relating to the core system.

[quote=", post:, topic:"]

@tal: On a slightly off-topic note, you said you’re a software developer (I assume professionally), and it seems you work with C++ quite a bit. What is the scope of that kind of software development in Pakistan?

[/quote]

IMHO the scope is not much as compared to say web development, i think there are ten or so companies in Karachi that have C++ jobs, most have financial projects/products and one or two of them have something interesting, There are more companies in Islamabad and Lahore but still not as much as i would like to see.

[quote=", post:, topic:"]
But in my personal experience in the Canadian software industry, companies tend to keep the core project teams back at their headquarters. Only the ‘trivial’ projects are outsourced to third world countries. What is your opinion regarding this issue?
[/quote]

Agreed, This is the case most of the times but there have been few exceptions too, I think a “core project” project would require very good computer science education, IMHO standard of education is very poor as compared to say US, secondly suitably experienced team which is not very easy to hire here as all the top-notch guys are already working overseas and lastly the security situation doesn’t allow that kind of investment.

^ Sounds like my take on the software development industry in Pakistan is pretty accurate. I would like to see Pakistani's do more to start their own companies and come up with their own products. Software is really not something which requires a lot of investment upfront so there is no excuse there. One can literally create a software product sitting in a garage surrounded by a couple PC's! Mainly technical skill is required, and when it comes to software, I find most developers are largely self-taught anyways.