clc-wiki answer to K+R exercise 2-7

Discussion in 'C Programming' started by vortura, May 16, 2010.

  1. vortura

    vortura Guest

    Hello all,

    I've been working through some of the exercises in the K&R book, and I
    think I might have found a bug in one of the answers on the CLC wiki.
    Exercise 2-7 asks for a function, invert(x, p, n) that returns x with
    the n bits starting at p inverted.

    http://clc-wiki.net/wiki/K&R2_solutions:Chapter_2:Exercise_7

    The answer listed on the wiki creates a mask of n 1's, then left
    shifts them by p before xor'ing with x. By left shifting the mask by
    p though, I think the mask is shifted past p, meaning the wrong bits
    are inverted by the XOR. I think the correct solution would left
    shift the mask by (p + 1 - n) instead. e.g.

    unsigned invert(unsigned x, int p, int n) {
    unsigned mask;
    mask = ~(~0U << n) << (p + 1 - n);
    return x ^ mask;
    }

    Is the answer in the wiki buggy, or have I made a mistake somewhere?

    regards,
    Richard
    vortura, May 16, 2010
    #1
    1. Advertising

  2. vortura <> writes:

    > I've been working through some of the exercises in the K&R book, and I
    > think I might have found a bug in one of the answers on the CLC wiki.
    > Exercise 2-7 asks for a function, invert(x, p, n) that returns x with
    > the n bits starting at p inverted.
    >
    > http://clc-wiki.net/wiki/K&R2_solutions:Chapter_2:Exercise_7
    >
    > The answer listed on the wiki creates a mask of n 1's, then left
    > shifts them by p before xor'ing with x. By left shifting the mask by
    > p though, I think the mask is shifted past p, meaning the wrong bits
    > are inverted by the XOR. I think the correct solution would left
    > shift the mask by (p + 1 - n) instead. e.g.


    The switch from p to p + 1 - n is just a re-interpretation of what p
    means. If p is the 0-based index of the LSB of the sequence, then the
    wiki solution is correct. If it is the index of MSB if the sequence
    then you are correct. I don't think K&R offer any definition so you are
    free to choose. Given that the wiki interpretation is simpler, I'd go
    with that one.

    > unsigned invert(unsigned x, int p, int n) {
    > unsigned mask;
    > mask = ~(~0U << n) << (p + 1 - n);
    > return x ^ mask;
    > }


    To invert these bits:

    ...00000xxx00

    you would call invert(x, 4, 3) -- the three bits at position 4 -- but
    the wiki solution considers this to be the 3 bits at position 2:
    invert(x, 2, 3).

    <snip>
    --
    Ben.
    Ben Bacarisse, May 17, 2010
    #2
    1. Advertising

  3. vortura

    Thad Smith Guest

    Ben Bacarisse wrote:
    > vortura <> writes:
    >
    >> I've been working through some of the exercises in the K&R book, and I
    >> think I might have found a bug in one of the answers on the CLC wiki.
    >> Exercise 2-7 asks for a function, invert(x, p, n) that returns x with
    >> the n bits starting at p inverted.
    >>
    >> http://clc-wiki.net/wiki/K&R2_solutions:Chapter_2:Exercise_7
    >>
    >> The answer listed on the wiki creates a mask of n 1's, then left
    >> shifts them by p before xor'ing with x. By left shifting the mask by
    >> p though, I think the mask is shifted past p, meaning the wrong bits
    >> are inverted by the XOR. I think the correct solution would left
    >> shift the mask by (p + 1 - n) instead. e.g.

    >
    > The switch from p to p + 1 - n is just a re-interpretation of what p
    > means.


    No, it's a re-interpretation of assignment order for "n bits starting at p" (in
    both cases p means p'th bit starting with bit 0 as LSB). Do you start at bit p
    and go through higher bit numbers or start at p and go through lower bit
    numbers? If I said "I want tickets for the three consecutive seats starting at
    seat 5", most people would expect me to get seats 5, 6, and 7, not 3, 4, and 5.

    --
    Thad
    Thad Smith, May 17, 2010
    #3
  4. Thad Smith <> writes:

    > Ben Bacarisse wrote:
    >> vortura <> writes:
    >>
    >>> I've been working through some of the exercises in the K&R book, and I
    >>> think I might have found a bug in one of the answers on the CLC wiki.
    >>> Exercise 2-7 asks for a function, invert(x, p, n) that returns x with
    >>> the n bits starting at p inverted.
    >>>
    >>> http://clc-wiki.net/wiki/K&R2_solutions:Chapter_2:Exercise_7
    >>>
    >>> The answer listed on the wiki creates a mask of n 1's, then left
    >>> shifts them by p before xor'ing with x. By left shifting the mask by
    >>> p though, I think the mask is shifted past p, meaning the wrong bits
    >>> are inverted by the XOR. I think the correct solution would left
    >>> shift the mask by (p + 1 - n) instead. e.g.

    >>
    >> The switch from p to p + 1 - n is just a re-interpretation of what p
    >> means.

    >
    > No, it's a re-interpretation of assignment order for "n bits starting
    > at p" (in both cases p means p'th bit starting with bit 0 as LSB). Do
    > you start at bit p and go through higher bit numbers or start at p and
    > go through lower bit numbers? If I said "I want tickets for the three
    > consecutive seats starting at seat 5", most people would expect me to
    > get seats 5, 6, and 7, not 3, 4, and 5.


    Which is what I thought I said. Is your point that I should have been
    more dogmatic about which one is correct? I.e. that interpreting p to
    be the MSB of the run being inverted is unusual enough to be wrong? If
    so, I won't disagree but I would not have made that point by starting a
    reply with "No..."!

    --
    Ben.
    Ben Bacarisse, May 17, 2010
    #4
  5. vortura

    vortura Guest

    On May 17, 12:00 am, Ben Bacarisse <> wrote:
    > The switch from p to p + 1 - n is just a re-interpretation of what p
    > means.  If p is the 0-based index of the LSB of the sequence, then the
    > wiki solution is correct.  If it is the index of MSB if the sequence
    > then you are correct.  I don't think K&R offer any definition so you are
    > free to choose.  Given that the wiki interpretation is simpler, I'd go
    > with that one.


    Thanks Ben. I see what you're saying - that there are a couple of
    ways in which p could be interpreted. The way I chose to interpret it
    was based on the getbits() example in K&R immediately preceding
    exercises 2-6 and 2-7, which says:

    'We assume that bit position 0 is at the right end and that n and p
    are sensible positive values. For example, getbits(x, 4, 3) returns
    the three bits in bit positions 4, 3, and 2, right adjusted.'

    If the same assumptions about p hold for the exercises, then I believe
    my answer is correct. Also, it seems that the wiki answers to
    exercises 2-6 and 2-7 each take a different approach. 2-6 takes p
    (like I have), as index of the MSB of the sequence, while 2-7 takes it
    to be the index of the LSB of the sequence.

    --
    Richard
    vortura, May 17, 2010
    #5
  6. vortura <> writes:

    > On May 17, 12:00 am, Ben Bacarisse <> wrote:
    >> The switch from p to p + 1 - n is just a re-interpretation of what p
    >> means.

    <snip>
    > If the same assumptions about p hold for the exercises, then I believe
    > my answer is correct. Also, it seems that the wiki answers to
    > exercises 2-6 and 2-7 each take a different approach. 2-6 takes p
    > (like I have), as index of the MSB of the sequence, while 2-7 takes it
    > to be the index of the LSB of the sequence.


    Yes, but as Thad Smith points out, taking "3 bits at position 4" to mean
    bits 2, 3 and 4 is a little odd to say the least. Those bits should
    designated "3 bits at position 2".

    --
    Ben.
    Ben Bacarisse, May 17, 2010
    #6
  7. vortura

    Seebs Guest

    On 2010-05-17, Ben Bacarisse <> wrote:
    > vortura <> writes:
    >> On May 17, 12:00 am, Ben Bacarisse <> wrote:
    >>> The switch from p to p + 1 - n is just a re-interpretation of what p
    >>> means.

    ><snip>
    >> If the same assumptions about p hold for the exercises, then I believe
    >> my answer is correct. Also, it seems that the wiki answers to
    >> exercises 2-6 and 2-7 each take a different approach. 2-6 takes p
    >> (like I have), as index of the MSB of the sequence, while 2-7 takes it
    >> to be the index of the LSB of the sequence.


    > Yes, but as Thad Smith points out, taking "3 bits at position 4" to mean
    > bits 2, 3 and 4 is a little odd to say the least. Those bits should
    > designated "3 bits at position 2".


    I'm not sure about that. It seems to me that the natural thing is to number
    bits by significance, so 0x01 is position 0, 0x02 is position 1, and so on.

    But if I am talking about consecutive digits, I normally count down. Three
    digits, starting in the millions place, is 111.....; so if position four is
    0b10000, then three bits starting at position four would be 0b11100, because
    it seems intuitive to me to count that way...

    .... But if we're talking about a numbered set of bits, it probably makes sense
    to go the other way.

    -s
    --
    Copyright 2010, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    Seebs, May 17, 2010
    #7
    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. Gregory Pietsch

    Implementation of functions in math.h on clc-wiki

    Gregory Pietsch, Mar 11, 2006, in forum: C Programming
    Replies:
    110
    Views:
    1,847
    Jordan Abel
    Mar 20, 2006
  2. Jordan Abel

    CLC wiki: faq

    Jordan Abel, Mar 21, 2006, in forum: C Programming
    Replies:
    4
    Views:
    300
    Steve Summit
    Mar 22, 2006
  3. Mike S
    Replies:
    8
    Views:
    413
    Netocrat
    May 21, 2006
  4. Alf P. Steinbach
    Replies:
    1
    Views:
    312
    Adam Aulick
    May 26, 2006
  5. Tony

    More posts in clc than in clc++ ?

    Tony, Feb 8, 2009, in forum: C Programming
    Replies:
    6
    Views:
    339
Loading...

Share This Page