12
\$\begingroup\$

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

\$\endgroup\$
11
  • 2
    \$\begingroup\$ why not bitwise "and"? \$\endgroup\$
    – rdans
    Aug 30, 2014 at 0:05
  • \$\begingroup\$ @Ryan Most people are more familiar with NAND gates than NOR gates :) \$\endgroup\$
    – Orby
    Aug 30, 2014 at 0:08
  • 1
    \$\begingroup\$ does recursion count as a loop? \$\endgroup\$
    – rdans
    Aug 30, 2014 at 1:21
  • \$\begingroup\$ @Ryan Recursion does count as a loop, though I'm not sure how you'd implement it without a conditional statement. \$\endgroup\$
    – Orby
    Aug 30, 2014 at 1:25
  • \$\begingroup\$ Is overflow defined or can I just output anything if it overflows? \$\endgroup\$
    – Comintern
    Aug 30, 2014 at 2:51

6 Answers 6

9
\$\begingroup\$

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])
\$\endgroup\$
9
\$\begingroup\$

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];
}
\$\endgroup\$
1
  • \$\begingroup\$ This is obviously a loophole, but +1 for pointing it out. \$\endgroup\$
    – Orby
    Sep 2, 2014 at 20:56
7
\$\begingroup\$

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.

\$\endgroup\$
0
7
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ If you're going to handle the wrap around that way, you could just cast to unsigned char. It's cleaner and more portable. \$\endgroup\$
    – Orby
    Aug 30, 2014 at 18:57
  • \$\begingroup\$ @Orby - I guess typing out unsigned doesn't come naturally to me in code golf. You're right of course - updated. \$\endgroup\$
    – Comintern
    Aug 30, 2014 at 23:41
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Orby
    Aug 30, 2014 at 6:59
2
\$\begingroup\$

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;
}
\$\endgroup\$
6
  • \$\begingroup\$ add(1, 255) is returning 128 for me, @Ryan. \$\endgroup\$
    – Orby
    Aug 30, 2014 at 2:02
  • \$\begingroup\$ @Orby its fixed now \$\endgroup\$
    – rdans
    Aug 30, 2014 at 2:08
  • \$\begingroup\$ % is not on the list of permitted operators, namely ~, |, >>, and <<. Maybe replace it with ands(x8|y8, 255)>>1? \$\endgroup\$
    – Orby
    Aug 30, 2014 at 2:11
  • \$\begingroup\$ Actually, ~(~x8 | y8 | 0xFFFFFF00) would do the trick nicely with only 4+ to your score. \$\endgroup\$
    – Orby
    Aug 30, 2014 at 2:21
  • 2
    \$\begingroup\$ But wouldn't making the type byte instead of int would make it overflow automatically? \$\endgroup\$ Aug 30, 2014 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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