Calculate n + 1 without using + or - or * or /

https://news.ycombinator.com/item?id=2721032

by namank • 15 years ago

18 17 15 years ago

news.ycombinator.com

As the title asks! My buddy came across this while preparing for an interview.

All I could think of is implementing a full adder in software but I'm thinking there has to be a better solution...help!

kirillzubovsky2• 15 years ago

Google quickly reveals this - http://nscraps.com/C/892-c-program-add-two-numbers-without-u...

hasenj• 15 years ago

I don't think this counts; it is using the sum operation, even if the operator doesn't look like +

awaage2• 15 years ago

how about this (example in ruby): def plus_1(x); arr = []; arr[x] = true; return arr.size; end

kirillzubovsky2• 15 years ago

Funny, this is the first thing I thought of, but then realized it would only work if x>0

awaage2• 15 years ago

oops! good catch!

custominstall2• 15 years ago

lol .. but also wont work for decimals

KeithMajhor• 15 years ago

Arbitrary addition, subtraction and multiplication without arithmetic signs.

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

int sub( int a, int b ) { return add( a, add( ~b, 1 ) ); }

int mul( int a, int b ) { int c = 0; while ( a ) { if ( a & 1 ) c = add( c, b ); a >>= 1; b <<= 1; } return c; }

alexl1988• 15 years ago

  int inc(int a) {
    int mask = ~a;
    /* Assuming a is 32-bit. If 64-bit, add 32-bit shift. */
    mask |= mask << 1;
    mask |= mask << 2;
    mask |= mask << 4;
    mask |= mask << 8;
    mask |= mask << 16;
    /* Take the longest run of 1s from the right of a.
     * mask has 0s there and 1s everywhere else. We want
     * to set the next bit to 1 and set the ones after
     * to 0. */
    return (a | ~(mask << 1)) & mask;
  }

code4pizza• 15 years ago

data Nat = Zero | Succ n

plus1 = Succ

Probably not the answer they were looking for, but it was the first thing that came into my head.

LarryA• 15 years ago

Could do lookup tables like the old CADET system did. http://www.websters-online-dictionary.org/definitions/IBM+16...

In some situations you may be data rich but function poor. Like embedded devices where you have a limited instruction set, 128bytes of RAM, but access to megs of ROM for program/data.

bobwebb• 15 years ago

def add_1(x): return sum([1,x])

Python.

Too simple? I didn't use any of the signs, and it demonstrates knowledge of the python standard library!

EDIT: Whoops, seems the idea of using the sum() function (or operator) has been dismissed elsewhere. Time to study some more languages, I think.

icebraining• 15 years ago

I have the proper Enterprise version:

    def increment(a):
        import urllib2
        url = "http://www.html2xml.nl/Services/Calculator/Version1/Calculator.asmx/Add?a=%d&b=1" % a       
        result = urllib2.urlopen(url).read() 
        from xml.dom.minidom import parseString
        result = parseString(result)
        return int(result.getElementsByTagName('int')[0].childNodes[0].data)

namank• 15 years ago

I'm pretty sure that's not a valid solution. Its the same as using Math.sum(). While it evaluates your resourcefulness, the point of the question, I think, is to figure out your knowledge and creative thinking

custominstall2• 15 years ago

php solution provided number is a positive int :

round($n.'.9')

anujkk• 15 years ago

If it is just about not using +,-,* or / operators, we can do it by using "++" operator.

x=n++;

alecbenzer• 15 years ago

if n is an integer, I believe this works:

https://gist.github.com/1063990

uses only bit shits, bitwise XOR, and bitwise AND

I would imagine they meant not to use the operations, not just the symbols.

veyron• 15 years ago

Basically replicate the carry process in the form of bit ops:

    def inc(n):
        x = 1
        while n & 1 == 1:
            n = n >> 1
            x = x << 1
        n = n | 1
        while not x == 1:
            x = x >> 1
            n = n << 1
        return n

Calculate n + 1 without using + or - or * or /

Related Stories