Bitmagic: Sum of 3 ints using a single "+"?

This is a discussion on Bitmagic: Sum of 3 ints using a single "+"? within the C Programming forums, part of the General Programming Boards category; We're trying to sum up three ints using a single + operator. This is part of a task from a ...

  1. #1
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210

    Bitmagic: Sum of 3 ints using a single "+"?

    We're trying to sum up three ints using a single + operator. This is part of a task from a course at the university, so please don't post any actual code. We'd just like to have some input, maybe an idea that leads us in the right direction.

    Basically we're given three ints and are supposed to return two, that when summed up by +, return the value that int1+int2+int3 would have returned. Of course we're not allowed to use - either. Just all of the other bitfield ops and !. We've already tried several "algorithms" that, unsurprisingly, didn't quite cut it

    In any case, a few things we tried (feel free to laugh at any point...):

    - We used int1&int2 to find bits where both are 1, (where + would produce a carry bit), shift the result 1 up and merge (|) this with (int1|int2). Return this as result1 and do the same for int2&int3.
    This yielded relatively good results. In most cases there was one carry bit too much in the final result. This is probably due to the way we try to find the carry bits. It's flawed as each carry bit changes the positions of the ones following. We didn't take this into account (and cannot, we're limited to 16 ops)

    - Tried to construct result1 with int1|(int2<<16) - in other words store int2 in the highword of our result. We then tried to construct result2 in a way that when summed up with result1, the effects of the shift cancel each other out. I guess it's appropriate to laugh at this point
    Any suggestions? This part of the task doesn't give a lot of points, so it's supposed to be fairly easy when compared to something like log2(x) - which I found a lot easier than this one


  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,420
    Bitwise addition
    0 + 0 = 0
    0 + 1 = 1
    1 + 0 = 1
    1 + 1 = 0 (carry 1)
    The addition you achieve with exclusive-or
    The carry you achieve with bitwise-and

    Wrap all that up in a loop and you should be there
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210
    Quote Originally Posted by Salem
    Wrap all that up in a loop and you should be there
    That would certainly work, but I forgot to mention that we are limited to ops and variable assignments only. No loops, no branching etc. That would be too simple :-)

  4. #4
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    When you subtract a negative of a number, it's the same as adding the positive number.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  5. #5
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210
    Quote Originally Posted by XSquared
    When you subtract a negative of a number, it's the same as adding the positive number.
    We're not allowed to use "-" either. I hope I mentioned that... yes

    I don't think we can even construct one here as it would require us to use a +, like ~myint +1 [or a -, like ~myint - (~0)].

    In any case, if I misread your post or thought too simple please say so. :-)
    Last edited by Nyda; 04-20-2004 at 10:11 AM.

  6. #6
    It's full of stars adrianxw's Avatar
    Join Date
    Aug 2001
    Posts
    4,831
    How about you put the single + sign in a macro or function which adds two integers.

    TempVar = Add(Int1, Int2);
    Result = Add(TempVar, Int3);

    or even

    Result = Add(Int3, (Add(Int1, Int2)));

    Only one + sign used. Up to you to do the macro...
    Wave upon wave of demented avengers march cheerfully out of obscurity unto the dream.

  7. #7
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210
    Quote Originally Posted by adrianxw
    How about you put the single + sign in a macro or function which adds two integers.
    No . We're limited to
    unary integer operations ! ~
    and
    binary integer operations & ^ | << >>

    Sorry if I wasn't precise about this. No macros, no functions, no pointermagic - pure bitmanipulations. The output has to be trough two ints which another function (that uses the one single +) sums up and returns. So yes, we can't even chose where that + is used.

    edit: Ok, we got it puzzled out. I can post it after deadline if anybody is interested in it. I don't think it's any faster than a simple "+" though.
    Last edited by Nyda; 04-20-2004 at 02:40 PM.

  8. #8
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    I think this would have some trick. You say you return 2 and then + the last one. If you get to use one + operator then why couldn't you use 0 maybe you don't return 2 and + the third one. Maybe their is some trick. I am now interested in solving it. and up to 16 operators huh? Interesting

  9. #9
    /*enjoy*/
    Join Date
    Apr 2004
    Posts
    159
    only specify me the goal of your program
    I want a goal very preci so that I can help you
    / * I use a translator of language then excuse me for makes a mistake them of grammar * /

  10. #10
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    thank you enjoy for translating your english is pretty good (just joking) From what I know you can not use the - and only use + once plus no loops and only 16 operators all of them either bitwise or ! operator.

  11. #11
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210
    The first idea we had turned out to be not so bad. We just had to change it so that something else moves our static carry bits. The one single + operator.
    I've posted the function in gray, highlight it if you want to read it. Or don't, if you want to puzzle it out on your own.

    Code:
    int sum3(int x, int y, int z) {
      int carries= ((x&y) | (x&z) | (y&z)) << 1;
      int ones=   (x ^ y) ^ z;
      return carries + ones;
     }
    The above code is as I remember it - I'm not at my computer at the moment - so there might be a typo in it.

    (x&y) | (x&z) | (y&z)
    will return all those bits set where x+y, x+z or y+z would produce a carry bit. << 1 shifts them one up where carry bits belong.
    x ^ y ^ z finds all those bits where the result would be either 1 or 1 and a carry bit. That is those where either only one of x,y,z has that specific bit set, or all of them.

    Finally the one single + produces carry bits for our static carry bits and yes, it even produces the correct result

    I would be surprised if this code is any faster than a single +... but who knows.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Application Repeatition
    By lgcarter in forum C Programming
    Replies: 3
    Last Post: 06-16-2009, 02:07 PM
  2. Minor Problem
    By stewie1986 in forum C Programming
    Replies: 6
    Last Post: 11-30-2007, 07:40 AM
  3. a sum equal to or in excess of 100
    By lyoncourt in forum C Programming
    Replies: 6
    Last Post: 10-07-2007, 05:43 PM
  4. combining int's into single int
    By chris1985 in forum C Programming
    Replies: 1
    Last Post: 05-08-2005, 02:07 PM
  5. string to int conversion not using atoi()
    By linucksrox in forum C Programming
    Replies: 2
    Last Post: 05-19-2004, 12:17 AM

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