-2
\$\begingroup\$

Given 2 positive integers in any format you'd like, return their sum using only logic gates and bit shifts (see example below). Don't worry about overflow.

EDIT: Using pre-written addition is obviously not allowed. So no a + b, Add(a, b), a - (-b) etc.

This is code golf, so standard loopholes apply. Shortest program in characters wins.

Some test cases:

3, 4 => 7
5, 7 => 12
9, 10 => 19
12, 31 => 43

Example code in C#, readable (471 characters):

int Add(int numA, int numB)
{
    int result = 0;
    int mask = 1;
    int carryOver = 0;
    while (numA > 0 || numB > 0)
    {
        int A_bit = numA & 1;
        int B_bit = numB & 1;
        if ((carryOver ^ A_bit ^ B_bit) == 1)
        {
            result |= mask;
        }
        carryOver = carryOver == 1 ? A_bit | B_bit : A_bit & B_bit;
        numA >>= 1;
        numB >>= 1;
        mask <<= 1;
    }
    return carryOver == 1 ? result | mask : result;
}

Example code in C#, unreadable (118 characters):

int r=0,m=1,c=0;while(a>0|b>0){int A=a&1,B=b&1;if((c^A^B)==1)r|=m;c=c==1?A|B:A&B;a>>=1;b>>=1;m<<=1;}return c==1?r|m:r;
\$\endgroup\$

closed as unclear what you're asking by xnor, Sriotchilism O'Zaic, Shaggy, Jo King, mbomb007 Jul 1 at 1:36

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 8
    \$\begingroup\$ I see what you're trying to do with this challenge, but it's basically hopeless to get answers that "play with bits" by banning arithmetic operators. There's too many ways to "cheat" with built-ins like sum and string concatenation, and trying to ban these leads to ambiguity and disagreements about the spirit of the challenge. After many attempts at such challenges, the community has come to the conclusion that Do X without Y challenges are a bad idea. \$\endgroup\$ – xnor Jun 30 at 19:11
  • 2
    \$\begingroup\$ See Patching out approaches and Non-observable requirements and other "Things to avoid". \$\endgroup\$ – xnor Jun 30 at 19:16
  • 3
    \$\begingroup\$ If we must use bit-bashing, then it should be more firmly stated, and not rely on the spurious leap that not using arithmetic operators would implicitly force us to "play with the bits." \$\endgroup\$ – gastropner Jun 30 at 19:30
  • 3
    \$\begingroup\$ @Bip Since it looks like you want to only allow functions on a whitelist, take a look at the atomic-code-golf tag. I think the best way to handle these is to describe a mini-language describing exactly what's allowed and how many points or characters each operation costs. \$\endgroup\$ – xnor Jun 30 at 19:41
  • 7
    \$\begingroup\$ using only logic gates and bit shifts But your example also uses logical branching (if, ?), loops (while), arithmetical comparisons (>)... I'm afrait it is going to be hard to define the allowed operations throughly and without making assumptions about language features \$\endgroup\$ – Luis Mendo Jun 30 at 21:03
3
\$\begingroup\$

JavaScript (ES6), 71 bytes

Takes input as (a)(b).

a=>g=(b,r=0,m=1,c,y=a&m,z=b&m)=>m?g(b,!(y^z)^!c?r|m:r,m<<1,c?y|z:y&z):r

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Looks like the spec (unnecessarily) requires input in binary. \$\endgroup\$ – Shaggy Jun 30 at 20:20
  • 2
    \$\begingroup\$ @Shaggy Neither the test cases nor the example code seem to do that, though. \$\endgroup\$ – Arnauld Jun 30 at 20:27
  • \$\begingroup\$ I think you overcomplicated it. \$\endgroup\$ – Daniil Tutubalin Jul 2 at 6:22
  • \$\begingroup\$ @DaniilTutubalin Definitely. It's just a port of the example code. \$\endgroup\$ – Arnauld Jul 2 at 10:29
3
\$\begingroup\$

JavaScript (ES6), 28 bytes

f=(a,b)=>b?f(a^b,(a&b)<<1):a

Try it online!

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Unicode), 13 bytesSBCS

Anonymous tacit prefix function. Takes list of two equal-length binary representations.

⊃(≠/,1⌽¨∧/)⍣≡

Try it online!

()⍣≡ apply the following function until two consecutive applications are identical:

∧/ AND of the two (lit. AND-reduce, so this enclose the result to reduce rank)

1⌽¨ shift the content of that enclosure a single step left

≠/, prepend the XOR of the two (lit. XOR-reduction, so this also encloses)

eventually the all carries have been done, so the second element (AND) is all-zero

 pick the first element

\$\endgroup\$
  • \$\begingroup\$ Hey, I've downvoted this answer since I don't think one ought to leave answers if they are unclear on the challenge requirements. I usually give people the benefit of the doubt when I am unclear on a challenge, but your comment asking if your answer is valid seems to indicate that you to are not entirely clear on what is allowed. \$\endgroup\$ – Sriotchilism O'Zaic Jun 30 at 21:07
  • 3
    \$\begingroup\$ @SriotchilismO'Zaic I had no doubt at the time of posting, since OP said without using the +, -, /, * operators of your language. However, after I posted, OP was edited to say only logic gates and bit shifts, leaving me in doubt, since I also use fix-point, concatenation, and selection. \$\endgroup\$ – Adám Jun 30 at 21:54
1
\$\begingroup\$

Logicode, 185 Bytes

Seeing as Logicode only has AND, OR, and NOT operators, I thought it might be fun to try to implement addition in Logicode for this challenge.

circ t(a,m)->cond a&m->1/0
circ x(a,b)->(a&!b)|(b&!a)
circ f(a,b,c,m,n)->cond n&10000000->0/f(a,b,(t(a,m)&(t(b,m)|c))|(t(b,m)&c),m+0,n+0)+x(x(t(a,m),t(b,m)),c)
circ a(a,b)->f(a,b,0,1,1)

Try it Online!

\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 65 bytes

+`(.?)(,\d*)(\d)
$2;$1$3
+`(.),
,;$1
{`00
0
01|10
1
}`;11
1;0
\D

Try it online! Link includes test cases in decimal; the header and footer perform base 2 conversion. Explanation:

+`(.?)(,\d*)(\d)
$2;$1$3
+`(.),
,;$1

Interleave the bits of both numbers, starting from the right.

{`00
0
01|10
1
}`;11
1;0

XOR each pair of bits together, and also AND the bits and carry 1 in that case. Repeat so that the carries propagate if necessary.

\D

Delete the separator punctuation.

\$\endgroup\$
1
\$\begingroup\$

C (gcc)

Not golfed to the max

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

Explanation, it's basically

while(b--)a++;

Will not work for negative b

Try it online

\$\endgroup\$

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