-1
\$\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\$
  • 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 '19 at 19:11
  • 2
    \$\begingroup\$ See Patching out approaches and Non-observable requirements and other "Things to avoid". \$\endgroup\$ – xnor Jun 30 '19 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 '19 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 '19 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 '19 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!

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

JavaScript (ES6), 28 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\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!

| improve this answer | |
\$\endgroup\$
2
\$\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

| improve this answer | |
\$\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

| improve this answer | |
\$\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\$ – Ad Hoc Garf Hunter Jun 30 '19 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 '19 at 21:54
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.

| improve this answer | |
\$\endgroup\$

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