hw c++ question!

[monkeyboi]

Hi,

After hrs of googling still couldn't find the answer to my question. I'm hoping i get better luck positng it here. Any C/C++ out there please help!!!

1)
a) Given an unsigned int x, what does x &= x-1; do and why does it work?

I know what x &= x-1 does but to explain why does it work, i have no clue.

b) How can the statement in a) be used in a C++ program to count set bits (ones) in a given unsigned int x? What is the advantage over looping through all bit positions?


thanks in advance.

[bwkaz]

And you're sure this isn't homework? (Hah! Questions that specific are almost always homework!)

[monkeyboi]

And you're sure this isn't homework? (Hah! Questions that specific are almost always homework!)


it is homework, i even say so in the title (hw)

[chameleon]

The &= operator looks at the binary representation of the values of x and the expression x-1 and does a bitwise AND operation on them.

Or you could say:

It performs a bitwise AND on the value of a variable (x) and the value of an expression (x-1) and assigns the result to the variable (x).

I'll work on your second point at lunchtime when I have a bit more time!

[chameleon]

Ok I think I've just solved your home work for you. I'll explain how it works but you'll have to write the code yourself.

If you feed a binary value into x and loop the entire expression until x is empty all you have to do is stick a variable that acts as a counter within the loop and whatever the counter equals is the number of 1's in the original value of x. For example:

1111 &= 1110 = 1110
1110 &= 1101 = 1100
1100 &= 1011 = 1000
1000 &= 0111 = 0000

Total loops = 4. Number of 1's in the original value of x = 4.

I think this is the answer although I would appreciate someone doing a bit more testing. I'm busy at work and I've ran out of space on the bcak of my fag packet.

[bwkaz]

it is homework, i even say so in the title (hw) Well, "hw" could also mean "hardware". In the future, I would spell out "homework" entirely. :)

We have a practice in this forum of not doing people's homework for them. (Or at least, some of us do... ;)) It's entirely possible that your professor (or teacher, if this is high school) is reading this forum; you don't want them to find out that you're having us do your homework for you, now, do you?

(Generally it's a MUCH better idea to go to the teacher/professor/whoever and ask them your question. That way they can give you the help you need while still ensuring you learn what you need to learn.)

[chameleon]

Well, "hw" could also mean "hardware". In the future, I would spell out "homework" entirely. :)

We have a practice in this forum of not doing people's homework for them. (Or at least, some of us do... ;)) It's entirely possible that your professor (or teacher, if this is high school) is reading this forum; you don't want them to find out that you're having us do your homework for you, now, do you?

(Generally it's a MUCH better idea to go to the teacher/professor/whoever and ask them your question. That way they can give you the help you need while still ensuring you learn what you need to learn.)

Although I probably sound like a hypocrite after previously helping I have to agree with the above comments. I didn’t know that this was the forum policy but from now on I’m onboard. While I find it hard to resist these little challenges I think it’s more important that people embarking on a course of education get that education.

[bwkaz]

Well, it's not any official "policy" (the closest thing is content that's deemed "in poor taste", although that doesn't really apply hardly at all -- I wonder whether and how we could get internet.com to add it to the AUP... hmm). It's just that as long as I can remember, people have frowned on doing other people's homework for them. ;)

[chameleon]

monkeyboi seems to have disappeared anyway, maybe he's in detention for not completing the assignment on time?!

[rocketpcguy]

either just ungrateful, or maybe didnt expect a reply.
but at least i learned a lot from your explanations, thanks! :)

[chameleon]

No problem rocketpcguy. That’s why I couldn’t resist doing it, the challenge and the need to learn! Ok, now I sound sad so I’m logging off!