PROBLEM...please READ

[Gagan]

//Problem Statement
//
//You work for a company that sells mechanical bit counting devices.
These devices
//wear out when they do a lot of counting. You are going to see how
much wear has
//been put on one particular 15-bit binary counter. One unit of wear
occurs for
//every bit that is flipped in the counter.
//
//For example:
//If the counter was at 7 = 000000000000111
//And it was incremented to 8 = 000000000001000
//
//Then 4 bits are flipped so 4 units of wear would occur. If a counter
was
//incremented through an inclusive range like 7 -> 12 then :
//Starts at 7 = 000000000000111
//Goes to 8 = 000000000001000 7 -> 8 = 4 units of wear
//Goes to 9 = 000000000001001 8 -> 9 = 1 unit of wear
//Goes to 10 = 000000000001010 9 -> 10 = 2 units of wear
//Goes to 11 = 000000000001011 10 -> 11 = 1 unit of wear
//Goes to 12 = 000000000001100 11 -> 12 = 3 units of wear
//This causes a total of 4+1+2+1+3 = 11 units of wear. Return the total
wear caused by incrementing the counter through the inclusive range
between start and finish.
//Definition
//
//Class: MechanicalCounter
//Method: amountWear
//Parameters: int, int
//Returns: int
//Method signature: int amountWear(int start, int finish)
//
//(be sure your method is public)
//
//
//Constraints
//-start will be less than finish.
//-start will be between 0 and 32766 inclusive.
//-finish will be between 1 and 32767 inclusive.
//
//Examples
//0)
//7
//8
//Returns: 4
//As seen above, 4 units of wear occur when 7 becomes 8.
//
//1)
//
//7
//12
//Returns: 11
//The example in the problem statement.
//
//2)
//1
//32767
//Returns: 65518

[Keith Thompson]

"Gagan" <In*******@gmail.com> writes:

//Problem Statement
//
//You work for a company that sells mechanical bit counting devices.

[snip]

No, I don't, so I guess I can't help you.

This looks very much like a homework problem, and you've made no
visible effort to solve it yourself.

If you really want us to do all the work for you, please give us your
instructor's e-mail address so we can submit the solution directly.
If not, show us some code, and we might be able to help.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Walter Roberson]

In article <11*********************@p10g2000cwp.googlegroups. com>,
Gagan <In*******@gmail.com> wrote:

//Class: MechanicalCounter
//Method: amountWear //Method signature: int amountWear(int start, int finish)

Methods do not exist in C. If you have a C++ question, you need to
ask it in comp.lang.c++ .

But it doesn't appear that you have a C++ question: it appears that
you have a homework problem and it appears that your implicit
question is whether someone will do your homework for you and allow
you to claim the credit.

If you have an -algorithm- question, then one of the programming
newsgroups might be appropriate -- but they are not likely to
help you unless you give an outline of your thinking on the
topic, and you give -specific- questions about the parts you
are unsure about.
I will go as far as to give you a hint: think about "exclusive or".
--
I was very young in those days, but I was also rather dim.
-- Christopher Priest

[manochavishal]

>>Problem Statement

You work for a company that sells mechanical bit counting devices.
These devices

I think you have just copied and pasted your assignment problem. No
body in this group will do the whole assignment for you. Its better if
you sit down and start solving it by yourself and then if you face any
difficulties you can paste it here.

Vishal

[Grumble]

Gagan wrote:

Return the total wear caused by incrementing the counter through
the inclusive range between start and finish.

Hint: consider popcount(i XOR i+1)

[manoj1978]

Gagan wrote:

//Problem Statement
//
//You work for a company that sells mechanical bit counting devices.
These devices
//wear out when they do a lot of counting. You are going to see how
much wear has
//been put on one particular 15-bit binary counter. One unit of wear
occurs for
//every bit that is flipped in the counter.
//
//For example:
//If the counter was at 7 = 000000000000111
//And it was incremented to 8 = 000000000001000
//
//Then 4 bits are flipped so 4 units of wear would occur. If a counter
was
//incremented through an inclusive range like 7 -> 12 then :
//Starts at 7 = 000000000000111
//Goes to 8 = 000000000001000 7 -> 8 = 4 units of wear
//Goes to 9 = 000000000001001 8 -> 9 = 1 unit of wear
//Goes to 10 = 000000000001010 9 -> 10 = 2 units of wear
//Goes to 11 = 000000000001011 10 -> 11 = 1 unit of wear
//Goes to 12 = 000000000001100 11 -> 12 = 3 units of wear
//This causes a total of 4+1+2+1+3 = 11 units of wear. Return the total
wear caused by incrementing the counter through the inclusive range
between start and finish.
//Definition
//
//Class: MechanicalCounter
//Method: amountWear
//Parameters: int, int
//Returns: int
//Method signature: int amountWear(int start, int finish)
//
//(be sure your method is public)
//
//
//Constraints
//-start will be less than finish.
//-start will be between 0 and 32766 inclusive.
//-finish will be between 1 and 32767 inclusive.
//
//Examples
//0)
//7
//8
//Returns: 4
//As seen above, 4 units of wear occur when 7 becomes 8.
//
//1)
//
//7
//12
//Returns: 11
//The example in the problem statement.
//
//2)
//1
//32767
//Returns: 65518

<OT>
In the same practise room.look at the room summary and view how
others solved that.
</OT>

[osmium]

"Gagan" writes:

//Problem Statement
//
//You work for a company that sells mechanical bit counting devices.
These devices
//wear out when they do a lot of counting. You are going to see how
much wear has
//been put on one particular 15-bit binary counter. One unit of wear
occurs for
//every bit that is flipped in the counter.

<snip>

Using pencil and paper make a truth table for the binary representation of n
for 0 to 15 in column one. Make column two the exclusive or of n and n+1.
Look for interesting relationships. Continue.

[Richard G. Riley]

On 2006-03-13, Gagan <In*******@gmail.com> wrote:

//If the counter was at 7 = 000000000000111
//And it was incremented to 8 = 000000000001000
//
//Then 4 bits are flipped so 4 units of wear would occur. If a counter

Looks like a college assignment so no complete answer. It also
mentioned your routine being "public" : are your sure you want C
and not C++?

Some guidelines to help you search for a solution:

1) What is it you are trying to find at a basic level? A) The number
of bits which have *changed*.
2) How do you do that? A) Use a bitwise exclusive or (XOR).
3) When you can see all the changed bits, what do you need to do next?
A) Count them. This might involve individual bit checks using
bitwise AND operation (&); Find examples in your C book or using google.

Good luck!

(Note this is the basic solution : the question asks for more than
that - it asks for the accumulation of changed bits when clicking from
"start" to "end" : this needs more thinking about).

[Micah Cowan]

"Richard G. Riley" <rg****@gmail.com> writes:

On 2006-03-13, Gagan <In*******@gmail.com> wrote:

//If the counter was at 7 = 000000000000111
//And it was incremented to 8 = 000000000001000
//
//Then 4 bits are flipped so 4 units of wear would occur. If a counter

Looks like a college assignment so no complete answer. It also
mentioned your routine being "public" : are your sure you want C
and not C++?

Some guidelines to help you search for a solution:

1) What is it you are trying to find at a basic level? A) The number
of bits which have *changed*.
2) How do you do that? A) Use a bitwise exclusive or (XOR).
3) When you can see all the changed bits, what do you need to do next?
A) Count them. This might involve individual bit checks using
bitwise AND operation (&); Find examples in your C book or using google.

There's a neat little trick for counting bits that I happened upon
recently. It's appealing because it's also divide-and-conquer. I won't
post an implementation, but... note that an octet could be considered
equivalent to eight 1-bit counts of how many bits could be found in
each bit position (always either zero or one). If you add the value of
each even bit position to the value of each odd position
(((value & 0xAA) >> 1) + (value & 0x55)), you'll end up with an octet
with four 2-bit counts of how many bits existed in each original
2-bit field. You can then add these 2-bit fields together to get 4-bit
counts, etc, until you have a count for the entire octet. And, of
course, you can expand this to work for 16-bit values, or whatever
else you need.

I ran across this while reading the source code for an implementation
of Minesweeper that guarantees to always generate solvable puzzles,
written by Simon Tatham (who also wrote the PuTTY terminal emulator
and telnet/ssh client). I asked him about it, and he'd forgotten where
he'd first seen it, but mentioned he'd seen it recently in the book
"Hacker's Delight", which is filled with similar bit-manipulation
techniques.

[Jordan Abel]

On 2006-03-14, Micah Cowan <mi***@cowan.name> wrote:

"Richard G. Riley" <rg****@gmail.com> writes:

On 2006-03-13, Gagan <In*******@gmail.com> wrote:

> //If the counter was at 7 = 000000000000111
> //And it was incremented to 8 = 000000000001000
> //
> //Then 4 bits are flipped so 4 units of wear would occur. If a counter
Looks like a college assignment so no complete answer. It also
mentioned your routine being "public" : are your sure you want C
and not C++?

Some guidelines to help you search for a solution:

1) What is it you are trying to find at a basic level? A) The number
of bits which have *changed*.
2) How do you do that? A) Use a bitwise exclusive or (XOR).
3) When you can see all the changed bits, what do you need to do next?
A) Count them. This might involve individual bit checks using
bitwise AND operation (&); Find examples in your C book or using google.

There's a neat little trick for counting bits that I happened upon
recently. It's appealing because it's also divide-and-conquer. I won't
post an implementation, but... note that an octet could be considered
equivalent to eight 1-bit counts of how many bits could be found in
each bit position (always either zero or one). If you add the value of
each even bit position to the value of each odd position
(((value & 0xAA) >> 1) + (value & 0x55)), you'll end up with an octet
with four 2-bit counts of how many bits existed in each original
2-bit field. You can then add these 2-bit fields together to get 4-bit
counts, etc, until you have a count for the entire octet. And, of
course, you can expand this to work for 16-bit values, or whatever
else you need.

A 256-element lookup table would almost definitely be faster.
I ran across this while reading the source code for an implementation
of Minesweeper that guarantees to always generate solvable puzzles,
written by Simon Tatham (who also wrote the PuTTY terminal emulator
and telnet/ssh client). I asked him about it, and he'd forgotten where
he'd first seen it, but mentioned he'd seen it recently in the book
"Hacker's Delight", which is filled with similar bit-manipulation
techniques.

[Micah Cowan]

Jordan Abel <ra*******@gmail.com> writes:

On 2006-03-14, Micah Cowan <mi***@cowan.name> wrote:

There's a neat little trick for counting bits that I happened upon
recently. It's appealing because it's also divide-and-conquer. I won't
post an implementation, but... note that an octet could be considered
equivalent to eight 1-bit counts of how many bits could be found in
each bit position (always either zero or one). If you add the value of
each even bit position to the value of each odd position
(((value & 0xAA) >> 1) + (value & 0x55)), you'll end up with an octet
with four 2-bit counts of how many bits existed in each original
2-bit field. You can then add these 2-bit fields together to get 4-bit
counts, etc, until you have a count for the entire octet. And, of
course, you can expand this to work for 16-bit values, or whatever
else you need.

A 256-element lookup table would almost definitely be faster.

Naturally. It would also require much more storage. Certainly the
lookup table is a better solution if you're going to be doing this
over and over again in a tight loop; but I wonder if it's worth it if
you're only doing it occaisionally? *Shrug*, depends on the application.

[Dave Thompson]

On 12 Mar 2006 19:37:42 -0800, "Gagan" <In*******@gmail.com> wrote:

//Problem Statement
//
//You work for a company that sells mechanical bit counting devices.
These devices
//wear out when they do a lot of counting. You are going to see how
much wear has
//been put on one particular 15-bit binary counter. One unit of wear
occurs for
//every bit that is flipped in the counter.

Advise them to switch to Grey coding. Saves wear, and also makes it
harder for first-term students to cheat on their homework.

- David.Thompson1 at worldnet.att.net