Implement an 8 bit adder

Question

The Challenge

Implement a function which accepts two integers whose values range from 0 - 255 and returns the sum of those integers mod 256. You may only use bitwise negation (~), bitwise or (|), bit shifting operators (>>,<<), and assignment (=).

Things you cannot use include (but are not limited to)

• Addition, subtraction, multiplication, and division
• Loops
• Conditional statements
• Function calls

Fewest uses of binary or, binary negation, and bit shift operations wins. In the event of a tie, the most popular solution wins. As always, standard loopholes apply.

Here is an example of a simple 2-bit adder. It uses 77 binary negations, 28 binary ors, and 2 bit-shifts for a total score of 107 (this can be seen by running the C preprocessor with gcc -E). It could be made much more efficient by removing the #defines and simplifying the resulting expressions, but I've left them in for clarity.

#include <stdio.h>
#define and(a, b) (~((~a)|(~b)))
#define xor(a, b) (and(~a,b) | and(a,~b))
int adder(int a, int b)
{
 int x, carry;
 x = xor(and(a, 1), and(b, 1));
 carry = and(and(a, 1), and(b, 1));
 carry = xor(xor(and(a, 2), and(b, 2)), (carry << 1));
 x = x | carry;
 return x;
}
int main(int argc, char **argv)
{
 int i, j;
 for (i = 0; i < 4; i++) {
 for (j = 0; j < 4; j++) {
 if (adder(i, j) != (i + j) % 4) {
 printf("Failed on %d + %d = %d\n", i, j, adder(i, j));
 }
 }
 }
}

Update: Added example and changed scoring critera

• rdans: why not bitwise "and"?
• Orby: @Ryan Most people are more familiar with NAND gates than NOR gates :)
• rdans: does recursion count as a loop?
• Orby: @Ryan Recursion does count as a loop, though I'm not sure how you'd implement it without a conditional statement.
• Comintern: Is overflow defined or can I just output anything if it overflows?

Answer 1

Python, 36 operations

A methods that's logarithmic in the parameter "8"!

def add(a,b):
 H = a&b #4 for AND
 L = a|b #1 
 NX = H | (~L) #2
 K = NX 
 H = H | ~(K | ~(H<<1)) #5
 K = K | (K<<1) #2
 H = H | ~(K | ~(H<<2)) #5
 K = K | (K<<2) #2
 H = H | ~(K | ~(H<<4)) #5
 carry = H<<1 #1
 neg_res = NX ^ carry #7 for XOR
 res_mod_256 = ~(neg_res|-256) #2
 return res_mod_256

The idea is to figure out which indices overflow and cause carries. Initially, this is just the places where both a andd b have a 1. But since carried bits can cause further overlows, this needs to be determined iteratively.

Rather than overflowing each index into the next one, we speed up the process by moving 1 index, then 2 indices, then 4 indices, being sure to remember places where an overflow happened (H) and where an overflow cannot happen any more (K).

---

A simpler iterative solution with 47 operations:

def add(a,b):
 H = a&b #4 for AND
 L = a|b #1 
 NX = H | (~L) #2
 c=H<<1 #1
 for _ in range(6): #6*5
 d = (~c)|NX
 e = ~d
 c = c|(e<<1)
 res = c ^ NX #7 for XOR
 res_mod_256 = ~(res|-256) #2
 return res_mod_256

---

Test rig, for anyone who wants to copy it.

errors=[]
for a in range(256):
 for b in range(256):
 res = add(a,b)
 if res!=(a+b)%256: errors+=[(a,b,res)]
print(len(errors),errors[:10])

Answer 2

C - 0

It does use operators outside of ~, |, >>, <<, and =, but I see solutions using casting and comma operators, so I guess the rule isn't too strict provided it isn't using the forbidden operators.

unsigned char sum(unsigned char x, unsigned char y)
{
 static unsigned char z[] = {
 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
 16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
 32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
 48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
 64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
 80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,
 96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,
 112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
 128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
 144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
 160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,
 176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
 192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
 208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
 224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,
 240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,
 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
 16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
 32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
 48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
 64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
 80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,
 96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,
 112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
 128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
 144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
 160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,
 176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
 192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
 208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
 224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,
 240,241,242,243,244,245,246,247,248,249,250,251,252,253,254
 };
 return (&z[x])[y];
}

• Orby: This is obviously a loophole, but +1 for pointing it out.

Answer 3

python, score = (削除) 83 (削除ここまで) 80

def g(x,y):
 for i in xrange(7):
 nx = ~x
 ny = ~y
 x,y = ~(x|ny)|~(nx|y), (~(nx|ny))<<1
 x = ~(x|~y)|~(~x|y)
 return ~(~x|256)

Unroll the loop. It's 10 ops per loop times 7 loops, 7 for the last xor, and 3 to squash the 9th bit at the end.

Implements the equation x+y = x^y + 2*(x&y) by repeating it 8 times. Each time there is one more zero bit at the bottom of y.

Answer 4

C, Score: (削除) 77 (削除ここまで) 60

Golfed just for the hell of it, (削除) 206 (削除ここまで) (削除) 169 (削除ここまで) 131 bytes:

#define F c=((~(~c|~m))|n)<<1;
a(x,y){int m=(~(x|~y))|~(~x|y),n=~(~x|~y),c;F F F F F F F return (unsigned char)(~(m|~c))|~(~m|c);}

Expanded:

int add(x,y)
{
 int m=(~(x|~y))|~(~x|y);
 int n=~(~x|~y);
 int c = 0;
 c=((~(~c|~m))|n)<<1; 
 c=((~(~c|~m))|n)<<1; 
 c=((~(~c|~m))|n)<<1; 
 c=((~(~c|~m))|n)<<1; 
 c=((~(~c|~m))|n)<<1; 
 c=((~(~c|~m))|n)<<1; 
 c=((~(~c|~m))|n)<<1; 
 return (int)((unsigned char)(~(m|~c))|~(~m|c));
}

Essentially the same solution (mathematically) that (削除) @KeithRandall (削除ここまで) @JuanICarrano came up with, but takes advantage of C's ability to play fast and loose with variable types and pointers to wipe everything after the first 8 bits without using any more operators.

Depends on the endian-ness of the machine and the sizeof() an int and a char, but should be able to be ported to most machine specific applications with the proper pointer math.

EDIT: This is a challenge that C (or other low level languages) will have a distinct upper hand at -- unless somebody comes up with an algorithm that doesn't have to carry.

• Orby: If you're going to handle the wrap around that way, you could just cast to unsigned char. It's cleaner and more portable.
• Comintern: @Orby - I guess typing out unsigned doesn't come naturally to me in code golf. You're right of course - updated.

Answer 5

Python - Score (削除) 66 (削除ここまで) 64

def xand(a,b):
 return ~(~a|~b) #4
def xxor(a,b):
 return (~(a|~b))|~(~a|b) #7
def s(a,b):
 axb = xxor(a,b) #7
 ayb = xand(a,b) #4
 C = 0
 for i in range(1,8):
 C = ((xand(C,axb))|ayb)<<1 #(1+1+4)x7=6x7=42
 return xxor(axb,xand(C,255)) #7 + 4 = 11
 #total: 7+4+42+11 = 64

It is the equation for a ripple adder. C is the carry. It is computed one bit at a time: in each iteration the carry is propagated left. As pointed out by @Orby, the original version did not make a modular addition. I fixed it and also saved a cycle in the iteration, as the first carry-in is always zero.

• Orby: Nice job, but your code does not wrap around properly (i.e. s(255,2) returns 257 rather than 1). You can correct this by changing your last line to return ~(~xxor(axb,C)|256) which adds 3 points.

Answer 6

C++ - score: 113

#define ands(x, y) ~(~x | ~y) << 1
#define xorm(x, y) ~(y | ~(x | y)) | ~(x | ~(x | y))
int add(int x, int y)
{
int x1 = xorm(x, y);
int y1 = ands(x, y);
int x2 = xorm(x1, y1);
int y2 = ands(x1, y1);
int x3 = xorm(x2, y2);
int y3 = ands(x2, y2);
int x4 = xorm(x3, y3);
int y4 = ands(x3, y3);
int x5 = xorm(x4, y4);
int y5 = ands(x4, y4);
int x6 = xorm(x5, y5);
int y6 = ands(x5, y5);
int x7 = xorm(x6, y6);
int y7 = ands(x6, y6);
int x8 = xorm(x7, y7);
int y8 = ands(x7, y7);
return (x8 | y8) % 256;
}

• Orby: add(1, 255) is returning 128 for me, @Ryan.
• rdans: @Orby its fixed now
• Orby: % is not on the list of permitted operators, namely ~, |, >>, and <<. Maybe replace it with ands(x8|y8, 255)>>1?
• Orby: Actually, ~(~x8 | y8 | 0xFFFFFF00) would do the trick nicely with only 4+ to your score.
• proud haskeller: But wouldn't making the type byte instead of int would make it overflow automatically?