Add Numbers deux — Bitwise Addition

Question

Your job is to implement bitwise addition.

To ensure that this is done, you will compute and print the result of addition without carry (or bitwise XOR). Then, you will compute the carry of the addition (bitwise AND) and multiply it by two (bitwise left shift). If the carry is nonzero, then you add the carry and the previous result until the carry is zero, at which point you stop producing output. If all is done correctly, the final result printed should be the sum of the two integers that you received as input.

Here's an ungolfed reference implementation in C:

#include <stdio.h>

void print_add(unsigned a, unsigned b)
{
    unsigned carry;

    while(b)
    {
        carry = a & b;
        a ^= b;
        printf("%u\n", a);
        b = carry << 1;
    }
}

Input

Two positive integers in any convenient format.

Output

A list of positive integers in any convenient format representing each result of addition without carry. Leading/trailing whitespace/newlines are allowed.

Rules

This is code-golf. The answer with the least bytes in each language wins, which means that I will not accept an answer.
Standard loopholes are forbidden. This includes, but is not limited to, Abusing native number types to trivialize a problem.

Testcases

1, 1 -> 0, 2
3, 17 -> 18, 16, 20
6, 7 -> 1, 13
21, 19 -> 6, 36, 32, 40
10, 9 -> 3, 19
20, 20 -> 0, 40

Your code must work for at least all pairs of positive integers that your integer type can represent the sum of.

This would have been far more interesting (at least to me) as an efficiency-golf challenge. — Cody Gray - on strike, Apr 29, 2020 at 22:32
@CodyGray As in fastest-code or fastest-algorithm? fastest-code would be somewhat hard to test and fastest-algorithm is trivial, it's used here. — S.S. Anne, Apr 29, 2020 at 22:34

Community · Accepted Answer · 2020-06-17 09:04:33Z

JavaScript (ES6), 34 bytes

Takes input as (A)(B), where A+B is a positive-looking 32-bit integer, i.e. less than 0x80000000.

Returns an array.

A=>g=B=>B?[A^=B,...g((B&~A)*2)]:[]

Try it online!

Or for 35 bytes, a BigInt version with unlimited input:

A=>g=B=>B?[A^=B,...g((B&~A)*2n)]:[]

Try it online!

How?

In order to use only 2 variables and pass a single variable to the recursive function, we apply the XOR right away to A and prepend the result to the output array.

Instead of computing (A AND B) * 2, we now need to compute (B AND (A XOR B)) * 2. Fortunately this can also be expressed as:

(B AND (NOT A)) * 2

leading to the rather short (B&~A)*2 in JS syntax.

Mitchell Spector · Accepted Answer · 2020-04-28 05:44:51Z

5

sed -En, 120 bytes

:L;s/0(.{8})0/a\1a/;s/0(.{8})1/b\1a/;s/1(.{8})0/b\1a/;s/1(.{8})1/a\1b/;tL;y/ab /01\
/;P;s/$/0/;tM;:M;s/\
.(.*1)/\
\1/;tL

Try it online!

Or try all the test cases online!

Input: Two 8-bit integers written in binary (on one line, with a space in between them).

Output: Also 8-bit binary numbers.

For convenience this is written for 8-bit integers, but if you want to use 32-bit integers, for instance, just change the instances of 8 in the script to 32. You can try out the 32-bit version here.

edited Apr 28, 2020 at 5:44

answered Apr 28, 2020 at 4:13

Mitchell Spector

7,9031 gold badge16 silver badges35 bronze badges

Add a comment |

Noodle9 · Accepted Answer · 2020-04-28 07:51:15Z

4

C (gcc), ^{65 \$\cdots\$ 46} 45 bytes

Saved 5 bytes thanks to ceilingcat!!!

f(a,b){for(;b;b&=~a,b*=2)printf("%d ",a^=b);}

Try it online!

edited Apr 28, 2020 at 7:51

answered Apr 27, 2020 at 23:22

Noodle9

19.9k3 gold badges20 silver badges45 bronze badges

\$\begingroup\$ I added a clarification so you don't need that long -- ugh. \$\endgroup\$
– S.S. Anne
Apr 27, 2020 at 23:31
\$\begingroup\$ @S.S.Anne Great - thanks for the clarification! :-) \$\endgroup\$
– Noodle9
Apr 27, 2020 at 23:53

Add a comment |

Léa Gris · Accepted Answer · 2020-04-30 11:04:38Z

4

Bash, ^{69 \$\cdots\$ 56} 45 bytes

11 bytes less, thank to Mitchell Spector!

d()(echo $[a=$1^$2];((c=$1&$2))&&d $a $[c*2])

Try it online!

Commented long version:

# Defines function d with parenthesis sub-shell block (commands), rather than
# curly-braces commands block, to save leading space and trailing semicolons.
d () 
(
  # Print and assign new value, using deprecated $[expression] syntax, rather
  # than modern's $((expression)) syntax, saves 2 bytes.
  echo $[a=$1^$2]
  # Bash stand-alone arithmetic expression's return-code, conditions recursive
  # call, with argument 2 computed inline, using deprecated but shorter
  # arithmetic expression.
  ((c=$1&$2)) && d $a $[c*2]
)

Note that the shorter but deprecated $[expression] syntax is going to be removed in later Bash versions.

See: man bash ^{Bash 5.0.3(1)-release}

Arithmetic expansion allows the evaluation of an arithmetic expression and the substitution of the result.

The format for arithmetic expansion is:
$((expression))
The old format $[expression] is deprecated and will be removed in upcoming versions of bash.

Python 2, 39 bytes

def f(a,b):1/b;print a^b;f(a^b,(a&b)*2)

Try it online!

A recursive function that prints all intermediate values, then terminates with an exception.

Python 2, 41 bytes

f=lambda a,b:b*[0]and[a^b]+f(a^b,(a&b)*2)

Try it online!

A recursive function that takes in two summands and returns a list of intermediate results.

edited Apr 27, 2020 at 23:15

answered Apr 27, 2020 at 22:49

Surculose Sputum

8,3331 gold badge12 silver badges40 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2020-04-27 23:46:23Z

Jelly, 12 11 bytes

&/Ḥṭ^/ƲƬḢ€Ḋ

A monadic Link accepting a list of two integers which yields a list of integers.

Try it online!

How?

Note that at the end of proceedings we'll have the sum and a carry of zero, and if we were to compute the addition without carry and the carry once more we'd get the same results, so we can keep going until [sum-without-carry, carry] does not change...

&/Ḥṭ^/ƲƬḢ€Ḋ - Link: list of two integers, [a,b]
       Ƭ    - Collect up (starting with [a,b]) while results are distinct applying:
      Ʋ     -   last four links as a monad:
 /          -     reduce (current pair, [x,y]) by:
&           -       bitwise AND
  Ḥ         -     double
     /      -     reduce (current pair, [x,y]) by:
    ^       -       bitwise XOR
   ṭ        -     tack -> [x^y, (x&y)*2]
        Ḣ€  - head each
          Ḋ - dequeue (remove a from the front)

Neil · Accepted Answer · 2020-04-28 00:10:05Z

3

Batch, 68 bytes

@if %2==0 exit/b
@set/a"a=%1^%2,b=(%1&%2)*2
@echo %a%
@%0 %a% %b%

Explanation:

@if %2==0 exit/b

Repeat until b is zero.

@set/a"a=%1^%2,b=(%1&%2)*2

Calculate the XOR and the carry.

@echo %a%

Output the next result.

@%0 %a% %b%

Restart with the new operands.

answered Apr 28, 2020 at 0:10

Neil

165k12 gold badges69 silver badges273 bronze badges

Add a comment |

Luis Mendo · Accepted Answer · 2020-04-29 09:56:35Z

MATL, 13 bytes

`Z~t1MZ&Et]xx

Try it online! Or verify all test cases.

Explanation

`       % Do...while
  Z~    %   Bitwise XOR. Takes the two inputs implicitly the first time
  t     %   Duplicate
  1M    %   Push the inputs of the latest bitwise XOR again
  Z&    %   Bitwise AND
  E     %   Multiply by 2
  t     %   Duplicate. This copy will be used as loop condition
]       % End. If the top of the stack is not 0 a new iteration is run
xx      % Delete top two elements (a 0 from the last bitwise AND and a
        % copy of the result from the last bitwise XOR)
        % Implicitly display

corvus_192 · Accepted Answer · 2020-04-29 18:56:14Z

3

Rust, 69 68 bytes

|mut a:u8,mut b:u8|while b>0{let c=(a&b)*2;a^=b;b=c;print!("{} ",a)}

A port of math junkie's python answer.

Try it on Rust Playground.

I had to use a temporary variable because destructuring in assignments is still being worked on

edited Apr 29, 2020 at 18:56

answered Apr 28, 2020 at 11:52

corvus_192

4,89912 silver badges23 bronze badges

\$\begingroup\$ I believe the trailing semicolon shouldn't be included in the byte count (as it is part of the assignment to g and not the closure), which saves a byte. \$\endgroup\$
– Endenite
Apr 29, 2020 at 18:47
\$\begingroup\$ You're probably right, as the code without the semicolon is an expression that evaluates to a closure, which could also be used as a return value. \$\endgroup\$
– corvus_192
Apr 29, 2020 at 18:55

Add a comment |

math junkie · Accepted Answer · 2020-04-27 23:02:27Z

2

Python 2, ⁴⁴ 43 bytes

-1 byte thanks to @SurculoseSputum

a,b=input()
while b:a,b=a^b,(a&b)*2;print a

Try it online!

Very simple implementation. Pretty much a golfed version of the reference code.

edited Apr 27, 2020 at 23:02

answered Apr 27, 2020 at 22:48

math junkie

7,2271 gold badge21 silver badges46 bronze badges

\$\begingroup\$ -1 byte by not using c. \$\endgroup\$
– Surculose Sputum
Apr 27, 2020 at 22:59
\$\begingroup\$ @SurculoseSputum Ah, thanks. I played around with that a little bit, but I didn't get the ordering quite right \$\endgroup\$
– math junkie
Apr 27, 2020 at 23:00

Add a comment |

Neil · Accepted Answer · 2020-04-27 23:44:07Z

Charcoal, 24 bytes

ＮθＮηＷη«≧＆θη≔⁻｜θιηθ≦⊗η⟦Ｉθ

Try it online! Link is to verbose version of code. Explanation:

ＮθＮη

Input a and b.

Ｗη«

Repeat while b is non-zero. This also makes a copy of b.

≧＆θη

Bitwise And b with a.

≔⁻｜θιηθ

Bitwise Or a with the copy of b, and subtract the above value, thus replacing a with the Bitwise Xor of a and b.

≦⊗η

Bitwise left shift b as it is now the carry.

⟦Ｉθ

Output the value of a on its own line.

Qwertiy · Accepted Answer · 2020-04-27 23:59:24Z

Javascript ES6, 48 chars, uint32 full support

a=>b=>{for(;b;alert(a>>>0))[a,b]=[a^b,(a&b)<<1]}

Test with console.log instead of alert:

f=a=>b=>{for(;b;console.log(a>>>0))[a,b]=[a^b,(a&b)<<1]}

g=(x,y,...res)=>console.log(`=== ${x} ${y} => ${res} ===`)+f(x)(y)

g(2147483648, 2147483648, 0)
g(3000000000, 1, 3000000001)
g(2147483648, 0)
g(1, 1, 0, 2)
g(3, 17, 18, 16, 20)
g(6, 7, 1, 13)
g(21, 19, 6, 36, 32, 40)
g(10, 9, 3, 19)
g(20, 20, 0, 40)

.as-console-wrapper.as-console-wrapper { max-height: 100vh }

Javascript ES6, 43 chars, int32 except 2**32

a=>b=>{for(;b;alert(a))[a,b]=[a^b,(a&b)*2]}

Test with console.log instead of alert:

f=a=>b=>{for(;b;console.log(a))[a,b]=[a^b,(a&b)*2]}

g=(x,y,...res)=>console.log(`=== ${x} ${y} => ${res} ===`)+f(x)(y)

g(2147483648, 2147483648, 0, 'never')
g(3000000000, 3000000000, 0, 1705032704)
g(3000000000, 1, 3000000001)
g(2147483648, 0)
g(1, 1, 0, 2)
g(3, 17, 18, 16, 20)
g(6, 7, 1, 13)
g(21, 19, 6, 36, 32, 40)
g(10, 9, 3, 19)
g(20, 20, 0, 40)

.as-console-wrapper.as-console-wrapper { max-height: 100vh }

Javascript ES 2020, 44 chars, infinite integers

a=>b=>{for(;b;alert(a))[a,b]=[a^b,(a&b)*2n]}

Test with console.log instead of alert:

alert=x=>console.log(x+"")

f=a=>b=>{for(;b;alert(a))[a,b]=[a^b,(a&b)*2n]}

g=(x,y,...res)=>console.log(`=== ${x} ${y} => ${res} ===`)+f(x)(y)

g(2147483648n, 2147483648n, 0, 4294967296)
g(3000000000n, 3000000000n, 0, 6000000000)
g(3000000000n, 1n, 3000000001)
g(2147483648n, 0)
g(1n, 1n, 0, 2)
g(3n, 17n, 18, 16, 20)
g(6n, 7n, 1, 13)
g(21n, 19n, 6, 36, 32, 40)
g(10n, 9n, 3, 19)
g(20n, 20n, 0, 40)

.as-console-wrapper.as-console-wrapper { max-height: 100vh }

psst neither 2^31 nor 2^32 can be represented in any traditional integer format (which Javascript's integer type is) — S.S. Anne, Apr 28, 2020 at 0:01
Formally js doesn't have integer type at all, only double. And BigInt from 2020 standard. — Qwertiy, Apr 28, 2020 at 0:07
interesting. Still, 32-bit signed two's complement has bitwise 0x80000000 as negative. — S.S. Anne, Apr 28, 2020 at 0:08

Olivier Grégoire · Accepted Answer · 2020-04-28 09:07:47Z

2

Java (JDK), 54 bytes

(a,b)->{for(;b>0;b=(b&~a)*2)System.out.println(a^=b);}

Try it online!

answered Apr 28, 2020 at 9:07

Olivier Grégoire

14.3k3 gold badges30 silver badges56 bronze badges

Add a comment |

Grimmy · Accepted Answer · 2020-04-28 10:03:20Z

2

05AB1E, 12 bytes

Δ`^=y`&D_#·)

Try it online!

answered Apr 28, 2020 at 10:03

Grimmy

15.6k1 gold badge33 silver badges63 bronze badges

Add a comment |

S.S. Anne · Accepted Answer · 2020-04-28 13:44:54Z

C# (Visual C# Interactive Compiler), 48 bytes

(a,b,c,d)=>{for(;b>0;c=a&b,d.Add(a^=b),b=c<<1);}

Try it online!

This is my first time using a for loop to do operations within the actual iterator, which feels weird, and uncomfortable, but also calming.

Mostly just tried to play with the reference, and make it more compact. Will be returning to this later. Need to double check my answer is fully legal (using the List), but this is my initial attempt.

More Info:

(a,b,c,d)=>{         //Pass in variables via lambda expression, and now a  for loop
                     //Note, the c# for statement format is: 
                     //for (initializer; condition; iterator)
                     ////body
                     //
    for(             //Start of for loop statement
        ;            //A mustache... jk. I am using no initializers, so just a ";" - totally blank
        b>0;         //My for loop conditional.  I used an int rather than a c bool, which is not as compact, maybe there's a better way        
                     //For loop Iterators:
        c=a&b,       //c is carry
        d.Add(a^=b), //Append to end of list: a equals a xor b
        b=c<<1       //left shift 
    )                //End Initializers, condition, and iterator parts of for loop           
    ;                //Body of for loop (nothing)
}                    //End lambda expression

I meant the link to an implementation. I've been curious to see what c# is like for a while. — S.S. Anne, Apr 28, 2020 at 3:09
I updated my code, sorry, I think that's what you meant right? — KaleSurfer, Apr 28, 2020 at 3:53
It looks like you removed the link that TIO puts in for C# in your answer. I'll add it back, hang on... (there are some templates for Code Golf if you click the chain link on the top middle). I run Linux so Microsoft's C# doesn't work for me. Since I know that TIO runs on Linux, I knew there had to be a free implementation. That turns out to be Mono. — S.S. Anne, Apr 28, 2020 at 13:43

mkst · Accepted Answer · 2020-04-29 21:36:57Z

K4, 32 31 bytes

Solution:

1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\

Examples:

q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\1 1
0 2
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\3 17
18 16 20
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\6 7
1 13
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\21 19
6 36 32 40
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\10 9
3 19
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\20 20
0 40

Explanation:

Lots of eaches...

1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\ / the solution
    (                        )\ / iterate
                        0b\:'   / convert each into into binary
                     @\:        / apply (@) each-left (\:) function to right
             (   ;  )           / two item list
                  &/            / AND
              ~=/               / XOR
         2/:'                   / convert each from binary
     1 2*                       / multiply first item by 1, 2nd by 2
   +                            / flip
  *                             / first
1_                              / drop first element

Stack Exchange Network

Add Numbers deux — Bitwise Addition

Input

Output

Rules

Testcases

16 Answers 16

JavaScript (ES6), 34 bytes

How?

sed -En, 120 bytes

C (gcc), ^{65 \$\cdots\$ 46} 45 bytes

Bash, ^{69 \$\cdots\$ 56} 45 bytes

Python 2, 39 bytes

Python 2, 41 bytes

Jelly, 12 11 bytes

How?

Batch, 68 bytes

MATL, 13 bytes

Explanation

Rust, 69 68 bytes

Python 2, ⁴⁴ 43 bytes

Charcoal, 24 bytes

Javascript ES6, 48 chars, uint32 full support

Javascript ES6, 43 chars, int32 except 2**32

Javascript ES 2020, 44 chars, infinite integers

Java (JDK), 54 bytes

05AB1E, 12 bytes

C# (Visual C# Interactive Compiler), 48 bytes

K4, 32 31 bytes

Your Answer

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

Linked

Hot Network Questions

Add Numbers deux — Bitwise Addition

Input

Output

Rules

Testcases

16 Answers 16

JavaScript (ES6), 34 bytes

How?

sed -En, 120 bytes

C (gcc), 65 \$\cdots\$ 46 45 bytes

Bash, 69 \$\cdots\$ 56 45 bytes

Python 2, 39 bytes

Python 2, 41 bytes

Jelly, 12 11 bytes

How?

Batch, 68 bytes

MATL, 13 bytes

Explanation

Rust, 69 68 bytes

Python 2, 44 43 bytes

Charcoal, 24 bytes

Javascript ES6, 48 chars, uint32 full support

Javascript ES6, 43 chars, int32 except 2**32

Javascript ES 2020, 44 chars, infinite integers

Java (JDK), 54 bytes

05AB1E, 12 bytes

C# (Visual C# Interactive Compiler), 48 bytes

K4, 32 31 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

C (gcc), ^{65 \$\cdots\$ 46} 45 bytes

Bash, ^{69 \$\cdots\$ 56} 45 bytes

Python 2, ⁴⁴ 43 bytes

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