Thread: Dealing with bits

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    18

    Dealing with bits

    i did my best to do this function, the following is what i came up with.
    However, the max operators that i can use is 12 and i'm using 16. i did all i
    can to have the min number of operatores and the min was 16 .Please Help!

    / * multFiveEight - multiplies by 5/8 rounding toward 0.
    * Examples: multFiveEights(77) = 48
    * multFiveEights(-22) = -13
    * You can assume |x| < (1 << 29)
    * Legal ops: ! ~ & ^ | + << >>
    * Max ops: 12
    * Rating: 3
    */
    Code:
    int multFiveEight(int x) {
      int negMask=1<<31;
      int pos=!(x&negMask);
      int ones=~0;
      int y=(x<<2)+x;
      int y_neg=(~(y>>4))+1;
      int y_pos=y>>3;
    return ((ones+pos)&y_neg)|((ones+!pos)&y_pos);
    }
    Last edited by Lina; 09-04-2006 at 11:21 AM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    18
    i edited it.

  3. #3
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Dividing a number by eight and bitshifting that number right by 3 is the same thing. That should help you cut down on the number of operations.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    18
    Can you clarify that more! what piece of code i should remove.

  5. #5
    The Richness... Richie T's Avatar
    Join Date
    Jan 2006
    Location
    Ireland
    Posts
    469
    I always hate these type of assignments because I place very little value on
    them - I highly doubt this appears in any real code, and for teaching purposes,
    either your brain is wired to do this type of thing in your sleep, or it isn't.

    Anyhoo, optimisations:

    Code:
    int negMask=1<<31;
    .
    .
    .
    int ones=~0;
    why exactly do you need operators to determine these constants? bit shifts do
    integer multiplication/division for you - if you shift a number left by n, you multiply
    it by a factor of 2^n (naturally assuming that no overflow occurs). So you can
    replace the first operation by just assigning this variable with the value of 2^31,
    and the ~ operator just inverts all the bits, so you can determine that value
    also.

    There's probably more you can do, but I won't try to go into more, but if you
    rethink your approach, you can do this in 3 operations!

    EDIT: Didn't think about signed numbers.
    Last edited by Richie T; 09-04-2006 at 06:16 PM.
    No No's:
    fflush (stdin); gets (); void main ();


    Goodies:
    Example of fgets (); The FAQ, C/C++ Reference


    My Gear:
    OS - Windows XP
    IDE - MS Visual C++ 2008 Express Edition


    ASCII stupid question, get a stupid ANSI

  6. #6
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Yes, I believe that's all there in these two lines.
    Code:
      int y=(x<<2)+x;
    Code:
      int y_pos=y>>3;
    There's the multiply by 5 and the divide by 8.

    The hard part is what else the assignment requires.

    My pet peeve it that when dealing with bits, signed values are used.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  7. #7
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Quote Originally Posted by Dave_Sinkula
    My pet peeve it that when dealing with bits, signed values are used.
    It shouldn't really matter, that's part of the joy of two's complement form for negative numbers. You should be able to use the bitwise math just the same.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  8. #8
    Registered User
    Join Date
    Oct 2004
    Posts
    151
    So what happens when the target architecture doesn't use two's complement for negative numbers?
    System: Debian Sid and FreeBSD 7.0. Both with GCC 4.3.

    Useful resources:
    comp.lang.c FAQ | C++ FQA Lite

  9. #9
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Quote Originally Posted by zx-1
    So what happens when the target architecture doesn't use two's complement for negative numbers?
    Is there a single platform made in the past 30 years* that doesn't?

    * Except machines made to operate on BCD
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  10. #10
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by Cat
    Is there a single platform made in the past 30 years* that doesn't?

    * Except machines made to operate on BCD
    Why does everyone ask this question backwards?

    If there ever was, is now, or ever will be why should I write my code so it breaks there rather than write it correctly?
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  11. #11
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Quote Originally Posted by Dave_Sinkula
    Why does everyone ask this question backwards?

    If there ever was, is now, or ever will be why should I write my code so it breaks there rather than write it correctly?
    Because the OP is learning how bitwise operations work, and bitwise operations on numbers require assumptions about the underlying representation of the numbers.

    I mean, hell, if it wasn't an exercise to learn about bitwise operations, the OP could just do y = 5 * x / 8; and be done with it.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  12. #12
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by Cat
    Because the OP is learning how bitwise operations work, and bitwise operations on numbers require assumptions about the underlying representation of the numbers.
    Or not, which is my point.

    Or rather, they should learn to use unsigned values with bits. Otherwise it's like learning how to ........ in the wind.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  13. #13
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    I don't believe there is ANY bitwise operation that can be guaranteed to work without assuming the underlying numeric representation. I mean, it would be theoretically legal for a platform to define, for example, "int" as a series of 8 BCD digits. Then, for example x << 2 and x * 4 are completely different results.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  14. #14
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by Cat
    I don't believe there is ANY bitwise operation that can be guaranteed to work without assuming the underlying numeric representation.
    Given the constraints of the language, this is demonstrably false [edit]with unsigned values[/edit].
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  15. #15
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    There are systems that use binary coded decimal for numbers... for example, the number 128 represented as 0001 0010 1000 in binary. In such a case 128 << 1 should yield 0010 0101 0000 (250) not 256. I know IBM mainframes once used BCD, I believe they still use some variant.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. SDLKey to ASCII without unicode support?
    By zacs7 in forum Game Programming
    Replies: 6
    Last Post: 10-07-2007, 03:03 AM
  2. Dealing with bits
    By V878 in forum C Programming
    Replies: 12
    Last Post: 10-02-2006, 05:25 PM
  3. Dealing with bits
    By ILoveVectors in forum C++ Programming
    Replies: 2
    Last Post: 07-02-2005, 07:02 PM
  4. Writing binary data to a file (bits).
    By OOPboredom in forum C Programming
    Replies: 2
    Last Post: 04-05-2004, 03:53 PM
  5. New idea on conveting byte to bits/bits to byte
    By megablue in forum C Programming
    Replies: 10
    Last Post: 10-26-2003, 01:16 AM