7
\$\begingroup\$

objective

write a program that can perform addition, subtraction, multiplication, and division, using only bit-wise operators, by bit-wise operators i mean the equivalent of JavaScript &, |, ^, ~, << ,>> ,>>>. (AND, OR, XOR, NOT, and SHIFTs)

rules

  • you can use other operators, just not for the actual operation/output. (i.e. loop-indentation is ok).
  • it need not actually take input, just be technically functional. (i.e. functions that take arguments).
  • any output is OK, you can even return a object with the sum, difference, etc.
  • you need not return floats for division ints are ok as well, you can round anyway you like.
  • as short as you can.
\$\endgroup\$
  • 6
    \$\begingroup\$ It's really unclear what the program is supposed to look like. Are you asking for a library of four functions that can take and return arbitrary ints (barring division by zero)? \$\endgroup\$ – breadbox Oct 2 '13 at 0:03
  • \$\begingroup\$ @breadbox its up to you, if you can make one function (i dont think this is practical) then knock yourself out. it has to be able to perform simple arithmetic on 32-bit integers. i hope my edit clarifies it a bit. \$\endgroup\$ – Math chiller Oct 2 '13 at 0:22
  • \$\begingroup\$ Do the function headers count against us, or only the function bodies? \$\endgroup\$ – John Dvorak Oct 2 '13 at 1:32
  • \$\begingroup\$ @JanDvorak i think they should count against, just like variables and their declarations. \$\endgroup\$ – Math chiller Oct 2 '13 at 1:41
  • \$\begingroup\$ Lambda expression ftw. Too bad if your language don't have them. \$\endgroup\$ – Johannes Kuhn Oct 2 '13 at 6:50
6
\$\begingroup\$

JavaScript, 124 119

a=(x,y)=>y?a(x^y,(x&y)<<1):x
s=(x,y)=>a(x,a(1,~y))
m=(x,y)=>x?a(y,m(s(x,1),y)):0
d=(x,y)=>(x=s(x,y))>>31?0:a(1,d(x,y))

Addition and Subtraction work for any signed numbers, multiplication and division only for unsigned (this hasn't been specified).

The input is assumed to be 32 bit.

I've been very strict and not even used comparison operators, except testing for equality with zero. It could probably be written a bit shorter otherwise.

\$\endgroup\$
  • \$\begingroup\$ javascript... 1.6? \$\endgroup\$ – John Dvorak Oct 2 '13 at 1:54
  • \$\begingroup\$ @JanDvorak … whatever works in Firefox \$\endgroup\$ – copy Oct 2 '13 at 1:55
  • \$\begingroup\$ @tryingToGetProgrammingStraight Here's a testcase: jsfiddle.net/MM66r \$\endgroup\$ – copy Oct 2 '13 at 2:10
  • 3
    \$\begingroup\$ A quick one character win: ~a(-1,y) is equivalent to a(1,~y). \$\endgroup\$ – Howard Oct 2 '13 at 5:43
  • 1
    \$\begingroup\$ You can save four bytes on your addition function, simply by letting it go one more iteration: a=(x,y)=>y?a(x^y,(x&y)<<1):x \$\endgroup\$ – primo Oct 21 '13 at 8:25
5
\$\begingroup\$

C, 313 characters

s(a,b){return a&b?s(a^b,(a&b)<<1):a^b;}
d(a,b){return s(s(a,~b),1);}
P(a,b,c){return b?P(a<<1,b>>1,b&1?s(c,a):c):c;}
p(a,b){return b<0?d(0,P(a,d(0,b),0)):P(a,b,0);}
q(a,b,c,z){long v=b=(z=b<0)?d(0,b):b,w=1;for(a=a<0?z^=1,d(0,a):a;a>=v;v<<=1)w<<=1;
for(c=0;b<=a;v<=a?a=d(a,v),c=s(c,w):0)v>>=1,w>>=1;return z?s(~c,1):c;}

The four functions are s = sum, d = difference, p = product, and q = quotient. P is an internal helper function used by p, and is not part of the API. (Note that despite q's definition, it should be invoked with only two parameters.)

Please note that p and q do not work by iterative addition/subtraction, but actually do the bitwise computation. (Otherwise q could be significantly shorter.) Thus their running time is a respectable O(log N).

All four functions accept the full range of positive and negative integers as inputs. Dividing by zero will produce an infinite loop, since there's no portable way to raise the appropriate exception.

Special note for C standards lawyers: The code assumes that sizeof(long) is strictly greater than sizeof(int), which is true more often these days than it used to be. If longs and ints are the same size, however, and the implementation sign-extends on right-shift (as most do), then q's valid input range is decreased such that the absolute value of the second argument cannot have its highest (non-sign) bit set. (Since dividing by such values can only be equal to zero or one, this isn't too much of a restriction in practice.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.