views:

1723

answers:

12

A friend and I are going back and forth with brain-teasers and I have no idea how to solve this one. My assumption is that it's possible with some bitwise operators, but not sure.

+1  A: 

Why not just incremet the first number as often, as the second number?

BeowulfOF
Incrementing is just adding 1, so the original issue still exists.
not really, INC and ADD are to different opcodes in machine language ;)
sindre j
+4  A: 

Cheat. You could negate the number and subract it from the first :)

Failing that, look up how a binary adder works. :)

EDIT: Ah, saw your comment after I posted.

Details of binary addition are here.

Andrew Rollings
+16  A: 

In C, with bitwise operators:

#include<stdio.h>

int add(int x, int y) {
    int a, b;
    do {
        a = x & y;
        b = x ^ y;
        x = a << 1;
        y = b;
    } while (a);
    return b;
}


int main( void ){
    printf( "2 + 3 = %d", add(2,3));
    return 0;
}
CMS
Thank you. I am afraid to ask, but does subtraction work similarly? I read that I can just add the two's complement. But when I try to, say, subtract 6-3, and turn that into 6+(-3) using two's complement, I get an infinite loop in the above algorithm.
add(6, -3) should work, you can play with the code here: http://codepad.org/iWSRSsUn
CMS
Left shifting a negative value is undefined behavior, it will work as expected on many processors but it isn't guaranteed, you should point this out in your answer. Also, can you add a \n to your printf statement? Aside from that, nice answer.
Robert Gamble
I tried converting your algorithm into Python (http://codepad.org/pb8IuLnY) and am experiencing an infinite loop when a negative number is passed in (i.e. the subtract). Are Python's operators any different than C?
@pomeranian.myopenid.com, it is most likely due to the way the left-shift operator is handled in Python. Instead of reaching an upper limit on the integer bits, and setting the highest bit to make a number negative, it becomes positive long integers.
Adam K. Johnson
+1  A: 

The reason ADD is implememted in assembler as a single instruction, rather than as some combination of bitwise operations, is that it is hard to do. You have to worry about the carries from a given low order bit to the next higher order bit. This is stuff that the machines do in hardware fast, but that even with C, you can't do in software fast.

Jonathan Leffler
+4  A: 

Define "best". Here's a python version:

len(range(x)+range(y))

The + there is list catenation, not addition.

Charlie Martin
A: 

Adding two integers is not that difficult; there are many examples of binary addition online.

A more challenging problem is floating point numbers! There's an example at http://pages.cs.wisc.edu/~smoler/x86text/lect.notes/arith.flpt.html

Colin
+1  A: 

Note, this would be for an adder known as a ripple-carry adder, which works, but does not perform optimally. Most binary adders built into hardware are a form of fast adder such as a carry-look-ahead adder.

My ripple-carry adder works for both unsigned and 2's complement integers if you set carry_in to 0, and 1's complement integers if carry_in is set to 1. I also added flags to show underflow or overflow on the addition.

#define BIT_LEN 32
#define ADD_OK 0
#define ADD_UNDERFLOW 1
#define ADD_OVERFLOW 2

int ripple_add(int a, int b, char carry_in, char* flags) {
    int result = 0;
    int current_bit_position = 0;
    char a_bit = 0, b_bit = 0, result_bit = 0;

    while ((a || b) && current_bit_position < BIT_LEN) {
        a_bit = a & 1;
        b_bit = b & 1;
        result_bit = (a_bit ^ b_bit ^ carry_in);
        result |= result_bit << current_bit_position++;
        carry_in = (a_bit & b_bit) | (a_bit & carry_in) | (b_bit & carry_in);
        a >>= 1;
        b >>= 1;
    }

    if (current_bit_position < BIT_LEN) {
        *flags = ADD_OK;
    }
    else if (a_bit & b_bit & ~result_bit) {
        *flags = ADD_UNDERFLOW;
    }
    else if (~a_bit & ~b_bit & result_bit) {
        *flags = ADD_OVERFLOW;
    }
    else {
        *flags = ADD_OK;
    }

    return result;
}
Adam K. Johnson
Wow, I'll try this out. Thanks!
Unfortunately the increment operator (current_bit_position++) requires addition. Nitpicky, I know.
@pomeranian.myopenid.com yeah, that is true in this case. In hardware, there is separate logic gates for each bit, and doesn't use a loop. If this loop were to be unrolled, you could use it without the ++ operator.
Adam K. Johnson
+3  A: 

No + right?

int add(int a, int b) 
{
   return -(-a) - (-b);
}
dfowler
In the question comments, @pomeranian.myopenid.com mentions that no arithmetic operators can be used. Besides, it would be better put as a - (-b) to use subtraction as the substitute operation.
Adam K. Johnson
A: 

an abacus will do this quite well, and it doesn't use any electricity!

Steven A. Lowe
+1  A: 

int add(int a, int b) { const char *c=0; return &(&c[a])[b]; }

A: 

CMS Can you please explain the logic? I am unable to understand your logic

+1  A: 

CMS's add() function is beautiful. It should not be sullied by unary negation (a non-bitwise operation, tantamount to using addition: -y==(~y)+1). So here's a subtraction function using the same bitwise-only design:

int sub(int x, int y) {
    unsigned a, b;
    do {
        a = ~x & y;
        b =  x ^ y;
        x = b;
        y = a << 1;
    } while (a);
    return b;
}
Deadcode