Velocity Reviews > PROBLEM...please READ

# PROBLEM...please READ

Gagan
Guest
Posts: n/a

 03-13-2006
//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
Guest
Posts: n/a

 03-13-2006
"Gagan" <(E-Mail Removed)> 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.velocityreviews.com/forums/(E-Mail Removed) <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
Guest
Posts: n/a

 03-13-2006
In article <(E-Mail Removed). com>,
Gagan <(E-Mail Removed)> 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@gmail.com
Guest
Posts: n/a

 03-13-2006
>>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
Guest
Posts: n/a

 03-13-2006
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@gmail.com
Guest
Posts: n/a

 03-13-2006

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
Guest
Posts: n/a

 03-13-2006
"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
Guest
Posts: n/a

 03-13-2006
On 2006-03-13, Gagan <(E-Mail Removed)> 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
Guest
Posts: n/a

 03-14-2006
"Richard G. Riley" <(E-Mail Removed)> writes:

> On 2006-03-13, Gagan <(E-Mail Removed)> 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
Guest
Posts: n/a

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

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post snoopy_@excite.com Java 3 04-07-2006 12:32 PM Doug ASP .Net 3 11-04-2005 07:35 PM Biz DVD Video 0 07-22-2005 03:44 AM Steve C++ 6 05-13-2004 05:54 PM Isaac VHDL 0 07-10-2003 01:43 PM

Advertisments