12
1
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
2why not bitwise "and"? – rdans – 2014-08-30T00:05:28.703
@Ryan Most people are more familiar with NAND gates than NOR gates :) – Orby – 2014-08-30T00:08:10.260
1does recursion count as a loop? – rdans – 2014-08-30T01:21:56.937
@Ryan Recursion does count as a loop, though I'm not sure how you'd implement it without a conditional statement. – Orby – 2014-08-30T01:25:38.727
Is overflow defined or can I just output anything if it overflows? – Comintern – 2014-08-30T02:51:53.510
@Comintern Your solution should wrap around, i.e. 255 + 3 should be equal to 2. – Orby – 2014-08-30T02:53:37.287
Is
x<<3
one operation or three? – xnor – 2014-08-30T06:08:45.747@xnor
x<<3
is one operation. – Orby – 2014-08-30T06:15:38.470Does (ab)using LEA counts as loophole? – PTwr – 2014-08-30T20:30:06.877
@PTwr That would depend on how you use it. If you're using it to perform addition of two registers, then yes. – Orby – 2014-08-30T20:55:18.857
@Orby then loophole it is. As this problem could be solved with single LEA it would be kinda cheating. – PTwr – 2014-08-30T21:46:47.623