PROBLEM...please READ

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

  1. Gagan

    Gagan Guest

    //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
    #1
    1. Advertising

  2. "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
    #2
    1. Advertising

  3. 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
    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
     
    Walter Roberson, Mar 13, 2006
    #3
  4. Gagan

    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
    #4
  5. Gagan

    Grumble Guest

    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
    #5
  6. Gagan

    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
    #6
  7. Gagan

    osmium Guest

    "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
    #7
  8. 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
    #8
  9. Gagan

    Micah Cowan Guest

    "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
    #9
  10. Gagan

    Jordan Abel Guest

    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
    #10
  11. Gagan

    Micah Cowan Guest

    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
    #11
  12. 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
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    4
    Views:
    523
    Chris Uppal
    May 5, 2005
  2. KK
    Replies:
    2
    Views:
    596
    Big Brian
    Oct 14, 2003
  3. MuZZy
    Replies:
    7
    Views:
    1,768
    Mike Hewson
    Jan 7, 2005
  4. sustle
    Replies:
    1
    Views:
    1,288
    sustle
    Jan 14, 2010
  5. mera
    Replies:
    7
    Views:
    1,114
Loading...

Share This Page