Discussion in 'C Programming' started by Gagan, Mar 13, 2006.

1. ### GaganGuest

//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

Gagan, Mar 13, 2006

2. ### Keith ThompsonGuest

"Gagan" <> 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) <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.

Keith Thompson, Mar 13, 2006

3. ### Walter RobersonGuest

In article <>,
Gagan <> 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

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

Walter Roberson, Mar 13, 2006
4. ### Guest

>>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

, Mar 13, 2006
5. ### GrumbleGuest

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)

Grumble, Mar 13, 2006
6. ### Guest

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>

, Mar 13, 2006
7. ### osmiumGuest

"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.

osmium, Mar 13, 2006
8. ### Richard G. RileyGuest

On 2006-03-13, Gagan <> 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).

Richard G. Riley, Mar 13, 2006
9. ### Micah CowanGuest

"Richard G. Riley" <> writes:

> On 2006-03-13, Gagan <> 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.

Micah Cowan, Mar 14, 2006
10. ### Jordan AbelGuest

On 2006-03-14, Micah Cowan <> wrote:
> "Richard G. Riley" <> writes:
>
>> On 2006-03-13, Gagan <> 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.

Jordan Abel, Mar 14, 2006
11. ### Micah CowanGuest

Jordan Abel <> writes:

> On 2006-03-14, Micah Cowan <> 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.

Micah Cowan, Mar 15, 2006
12. ### Dave ThompsonGuest

On 12 Mar 2006 19:37:42 -0800, "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.

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

Dave Thompson, Mar 20, 2006