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 #define
s 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