A Standard CS introductory problem

This is a discussion on A Standard CS introductory problem within the C++ Programming forums, part of the General Programming Boards category; Hello, everyone. I'm not a CS major, but I just nosing around CS department pages and occasionally try to solve ...

  1. #1
    Registered User
    Join Date
    Oct 2005
    Posts
    271

    A Standard CS introductory problem

    Hello, everyone.

    I'm not a CS major, but I just nosing around CS department pages and occasionally try to solve the problems that are posted.

    I guess some of you are familiar with the "twiddling bits" problem.

    Like creating an AND function with just ~ and |.

    Well, I'm stumped on this one.
    Code:
    /* 
     * evenBits - return word with all even-numbered bits set to 1
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 8
     *   Rating: 2
     */
    int evenBits(void) {
        return 2;
    }
    My compiler has 32bit integers, so even allowing that max ops is 16 and not 8, I can't seem to solve it without using some 32 operands.

    The site said I'm not supposed to use loops but just to make the code shorter, here's what I did.

    Code:
    int evenBits(void) {
    	int i, j;
    	i = 0;
    	for(j = 31; j > 0; j -= 2)
    		i |= (1 << j);
        return i;
    }
    Counting the times I use | and <<, it's about 32 times, I guess.
    Is there a way to do this with just 16 (or 8)?

  2. #2
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    evenBits - return word with all even-numbered bits set to 1
    Huh?

  3. #3
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,069
    Yeah, that's the part where you lost me as well, but then I don't know enough about bitwise operations to really start any questions.
    Sent from my iPadŽ

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,325
    >> Huh?

    10101010101010101010101010101010

  5. #5
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,069
    I think I get the even numbered bits part, it's the "return word" that I'm not getting.
    Sent from my iPadŽ

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,325
    It means word as in natural size of data on the machine (in this case 32 bits).

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,325
    Try thinking about how to combine the current state of the bits with a modified version of the current state of the bits to set multiple bits at the same time. For example, if you had 0000000010101010, how would you get it to be 1010101010101010 in one line of code (but potentially multiple operations).

  8. #8
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398
    Ah, here's the secret:

    The bitwise operators operate on ALL of the bits at once.

    So, if you perform a bitwise OR between the unknown and 55555555 hex (1,431,655,765 decimal), you will set all of the even bits to one.

    55555555 hex = 0101 0101 0101 0101... binary.

    That's the other secret... Always use hex when manipulating bits. Its easier (for humans) to convert between hex and binary, than between decimal and binary.

    Note - It is conventional to start counting bits with the LSB (least significant bit) as "bit-0". Using that convention, bit-0 is even, and the MSB (bit-31) is odd.

  9. #9
    Registered User
    Join Date
    Oct 2005
    Posts
    271
    I understood Daved's hint. And I got the following code.

    Code:
    int evenBits(void) {
    	int i;
    	i = 1 << 1;
        i |= i << 2;
        i |= i << 4;
        i |= i << 8;
        i |= i << 16;
        return i;
    }
    That would suffice, right? So I managed to do it with 9 of the designated operands.

    But I'm afraid I'm not getting what dougdbug is saying. I understand that
    55555555 hex = 0101 0101 0101 0101... binary
    but doesn't that defeat the purpose of trying to set the bits that way through a set of operations?
    Or is there something that I'm missing here?

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,325
    I think DougDbug was assuming that the function should take in some unknown number and convert it to be all even bits on. I understood the task to mean start from scratch and use bit manipulation to do the task. If you use his interpretation it wouldn't make as much sense, since you could do it in only 2 operations.

    My quick solution was similar to yours, also using 9 operands. If DougDbug was right about the first bit being bit-0 (i.e. 01010101010101010101010101010101), then you can make your code use only 8 operands, so that just might be the answer.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  2. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  3. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  4. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 05:24 PM
  5. problem with my font manager
    By hannibar in forum C Programming
    Replies: 1
    Last Post: 03-07-2006, 07:03 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21