Thread: 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

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 :-)

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

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 * /

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.

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.