Thread: Tough Bitwise Exercise

  1. #1
    Registered User
    Join Date
    Jun 2005
    Posts
    32

    Post Tough Bitwise Exercise

    I am just lost on this one, its got me baffled.

    A function is passed a Signed 32 bit integer.
    This function must return EXACTLY 1 or 0 (i.e. it returns int not bool)
    You are allowed to use the following bitwise operations a maxium of 10 times.
    Code:
     Legal ops: ~ & ^ | + << >>
    You can create as many Variables as needed, and can use the assignment operator as many times as needed.

    You cannot use any conditional operators (if() ()?: while() for() etc...)

    Detect if the given integer is non-zero or 0.

    Essentially use only bitwise operations and return an integer that is either 1 or 0 to indicate if the passed integer is non zero or not.


    Now i have personally had a very tough time with this one, and if anyone has any idea how to solve it, or an idea on how to do it, please share =).


    Good luck

    EDIT: The Biggest problem i am having is that with only 10 operations i can't find a (foolproof) way to check enough bits to ensure i won't miss one on the odd chance that said number falls on the single bit i don't check.

    Thanks again for any info.

  2. #2
    Dump Truck Internet valis's Avatar
    Join Date
    Jul 2005
    Posts
    357
    Can you use -, I see + so just double checking?

    (value - 0x01010101) & ~value & 0x80808080) + 1 ; should work, I guess you could also set a negative and add that. That checks a single word for a 0, so do that shift right 16, do it again, and then or the two and return.

    oh, I lied, keep searching
    Last edited by valis; 09-07-2005 at 11:06 PM.

  3. #3
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    Code:
    int mask(int & price)
    {
        int free = 1024;
        free = free & price;
        free = free << 31;
        return free
    }
    I cant think please don't ban me.

  4. #4
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Hint: think divide and conquer.

  5. #5
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    oh hell a hint, I guess you dont want to tell us

    I wasn't thinking and I didn't see it was signed so this means it can be in twos compliment. lets see 11 = -3 ? and 011 = 3 correct.

    Help me out am I way off.

  6. #6
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    Ohh damit signed means positive, unsigned either or. I give just call me Newb as I try to learn.

  7. #7
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by valis
    Can you use -, I see + so just double checking?

    (value - 0x01010101) & ~value & 0x80808080) + 1 ; should work, I guess you could also set a negative and add that. That checks a single word for a 0, so do that shift right 16, do it again, and then or the two and return.

    edit: my writing may have been cryptic so:
    ret = (value - 0x01010101) & ~value & 0x80808080) + 1 ;
    value >>= 16 ;
    ret |= (value - 0x01010101) & ~value & 0x80808080) + 1;

    8 bitwise operators in total.
    I think the original question was worded so that only the listed operators are allowable. Above I see -, &, ~, &, +, >>, |, -, &, ~, &, and +, in that order from left to right. (Only = is allowed in the problem, so I treat |= and >>= as operators.) Subtraction is tolerable, but that's more than ten operators.

    Also, your code does not seem to work for me, but I'm guessing where you want an open parenthesis placed.

  8. #8
    Registered User
    Join Date
    Jun 2005
    Posts
    32
    Thanks for all the respones, - is a vaild operator sorry i forgot it. As for the code posted, it doesn't work for me either, i get a constant -2134252232 or somthing. Any all good thoughts up to this point, i will continue to work on it.

  9. #9
    Dump Truck Internet valis's Avatar
    Join Date
    Jul 2005
    Posts
    357
    yeah, it worked at first (actually I must have only thought it worked), it came from a set of really useful bit manipulation sites I have bookmarked:
    http://graphics.stanford.edu/~seander/bithacks.html
    http://aggregate.org/MAGIC/

    At the bottom of both sites they have more links, hope that helps

    edit: I have no idea what I initially did because I can't reproduce it, but it would always result in 0 or -1 (that's what the + 1 was for)

  10. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    32
    well you can easily get that on Odd numbers.

    return(value<<31)>>31;

    This will return 0 on even and -1 on odd, but i need 0 on 0 and 1 on all all non zero numbers.

    Thanks for the links i will check them out.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Line of data input method
    By larry_2k4 in forum C Programming
    Replies: 2
    Last Post: 04-28-2009, 11:34 PM
  2. Bitwise Questions
    By someprogr in forum C Programming
    Replies: 8
    Last Post: 12-14-2008, 06:45 PM
  3. C bitwise operator exercise - more like newb killer
    By shdwsclan in forum C Programming
    Replies: 3
    Last Post: 02-22-2006, 07:02 AM
  4. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM