Calculate n + 1 without using + or - or * or / | Hacker News Reader

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

18 pointsnamank17 comments

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!

View on HN

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; }

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)

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

  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;
  }

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.

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

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

x=n++;

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

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

oops! good catch!

lol .. but also wont work for decimals

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

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

php solution provided number is a positive int :

round($n.'.9')

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.

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.

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.

Reply on news.ycombinator.com