Thread: Bit puzzle help

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    1
    Rep Power
    0

    Bit puzzle help


    Can you explain how the following two "bit puzzles" achieve what the title of the problems say they do.

    1. Absolute Value
    int abs(int x){
    int sign = x >> 31;
    int neg_x = ~x+1; //two's compliment
    return (neg_x & sign) | (x & ~sign);
    }

    2. Lazy Addition
    // assumes a + b + c + d <= 127
    // and that a,b,c,d are all positive
    // returns a + b + c + d using only 2 additions
    int add4(int a, int b, int c, int d){
    x = a << 8 | b;
    y = c << 8 | d;
    int q = x + y;
    return (q & 0xff) + (q >> 8);
    }

    All the explanation in the world would be extremely helpful and appreciated!! Thank you!
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,392
    Rep Power
    1871
    There are more here, with explanations.
    Perhaps it will help you figure it out.
    bit hacks
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,638
    Rep Power
    4247
    Cute stuff. HINTS:

    1. Print out the results of (neg_x & sign) and (x & ~sign) separately. Then convert them into binary and you'll get an idea of what the | does (it is pretty easy once you see the two results in binary to figure out what is going on)

    2. The reason why this works is because initially the numbers all occupy one byte of (an assumed 32 bit) int. i.e. the numbers are of the format 000a, 000b, 000c, 000d. By bit shifting the bits, it essentially makes two variables
    X = 00ab
    Y = 00cd
    where each variable occupies one byte of the int (this is why there is a restriction that a, b, c and d are <= 127) Again, printing x, y in binary along with a and n will tell you exactly what is happening

    Now it adds the numbers, which will add the numbers on individual bytes like this:
    Q = 00(a+c)(b+d)
    Again, if you print Q in binary, you'll see what is going on. Also note here the restriction that 0 <= a, b, c, d <= 127. Because if the result of (b+d) is > 255, then it will overflow into the calculation of (a+c). Overflows cannot happen if both numbers are <= 127.

    The final step is to separate byte (b+d) and byte (a+c) and then add them together to get the final result.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo

IMN logo majestic logo threadwatch logo seochat tools logo