/* CHALLENGE : A Byte of multiplication. First step: You're allowed to: - use integers 0 and 1 (only) - use the assignment operator '=' (but no '==') - create and use variables - create and use arrays - use array indexing, no slicing (as far as you respect the first rule) - create and use functions - anything else is FORBIDDEN (no loop, no if, no +* /-, no >==<, no <<>>^&|, no dictionaries, no strings, no tuples, no sets, no import, no built-ins, etc...) Your goal is to create a function for each logic operator: yes,not,and,or,xor,nand,nor,nxor,lower than, greater than, equal to ex: yes(1) -> 1 and(0,1) -> 0 nxor(1,0) -> 0 Second step: With the same tools, your task is to build functions able of: - add 2 8-bits-bytes - subtract 2 8-bits bytes - multiply 2 8-bits-bytes. To respect the rules, bytes will be built as lists of 0 and 1 ex: bAdd([0,0,1,1,1,0,1,0],[0,1,0,0,1,0,0,1]) -> [1,0,0,0,0,0,1,1] (58+73 = 131) bSub([0,1,0,0,1,0,0,1],[0,0,1,1,1,0,1,0]) -> [0, 0, 0, 0, 1, 1, 1, 1] (73-58 = 15) bMul([0,0,0,0,0,1,1,1],[0,0,0,1,1,1,0,1]) -> [1,1,0,0,1,0,1,1] (7*29 = 203) your functions don't need to deal with cases involving negative or >255 integers. Bonus: Grail goes to who uses some recursion ! (there are multiple grails) https://www.sololearn.com/post/167428/?ref=app */ #include #include #include #include using namespace std; using bits = vector; using Bits = vector; // Identity auto Identity = [](int x) { return x; }; // NOT // NOT(0) = 1 // NOT(1) = 0 auto NOT = [](int x) { return bits{1, 0}[x]; }; // AND // 0 AND 0 = 0 // 0 AND 1 = 0 // 1 AND 0 = 0 // 1 AND 1 = 1 auto AND = [](int x, int y) { return Bits{{0, 0}, {0, 1}}[x][y]; }; // OR // 0 AND 0 = 0 // 0 AND 1 = 1 // 1 AND 0 = 1 // 1 AND 1 = 1 auto OR = [](int x, int y) { return Bits{{0, 1}, {1, 1}}[x][y]; }; // XOR // 0 XOR 0 = 0 // 0 XOR 1 = 1 // 1 XOR 0 = 1 // 1 XOR 1 = 0 auto XOR = [](int x, int y) { return Bits{{0, 1}, {1, 0}}[x][y]; }; // NAND // 0 NAND 0 = 1 // 0 NAND 1 = 1 // 1 NAND 0 = 1 // 1 NAND 1 = 0 auto NAND = [](int x, int y) { return NOT(AND(x, y)); }; // NOR // 0 NOR 0 = 1 // 0 NOR 1 = 0 // 1 NOR 0 = 0 // 1 NOR 1 = 0 auto NOR = [](int x, int y) { return NOT(OR(x, y)); }; // XNOR // 0 XNOR 0 = 1 // 0 XNOR 1 = 0 // 1 XNOR 0 = 0 // 1 XNOR 1 = 1 auto XNOR = [](int x, int y) { return NOT(XOR(x, y)); }; // EQUAL // 0 EQU 0 = 1 // 0 EQU 1 = 0 // 1 EQU 0 = 0 // 1 EQU 1 = 1 using T = decltype(XNOR); T EQU = XNOR; // GREATER THAN // 0 GT 0 = 0 // 0 GT 1 = 0 // 1 GT 0 = 1 // 1 GT 1 = 0 auto GT = [](int x, int y) { return AND(EQU(x, 1), EQU(y, 0)); }; // LESS THAN // 0 LT 0 = 0 // 0 LT 1 = 1 // 1 LT 0 = 0 // 1 LT 1 = 0 auto LT = [](int x, int y) { return AND(EQU(x, 0), EQU(y, 1)); }; //Left shift auto LSH = [](bits b) { //return bits{b[1], b[2], b[3], b[4], b[5], b[6], b[7], 0u}; rotate(begin(b), begin(b)+1, end(b)); *(end(b)-1) = 0; return b; }; // Addition core struct add_b { int operator()(int l, int r) { int xorab = XOR(l, r); int res = XOR(xorab, c); c = OR(AND(xorab, c), AND(l, r)); return res; } int c = 0; // carry }; // Subtractor core struct sub_b { int operator()(int l, int r) { int xorab = XOR(l, r); int res = XOR(xorab, b); b = OR(AND(NOT(xorab), b), AND(NOT(l), r)); return res; } int b = 0; // borrow }; // Apply the passed function to each elements lhs and rhs simultaneously template auto Apply(T &&lhs, T &&rhs, U toapply) { bits res{lhs}; transform(rbegin(res), rend(res), rbegin(rhs), rbegin(res), toapply); return res; } auto Print = [](auto &&toprint) { for (auto e : toprint) cout << e << ' '; cout << "\n\n"; }; // exposed user interface auto AddB = [](auto &&a, auto &&b) { return Apply(a, b, add_b{}); }; auto SubB = [](auto &&a, auto &&b) { return Apply(a, b, sub_b{}); }; //Multiplication core struct mul_b { mul_b(bits const &lhs, bits &res) :Lut{{0,0,0,0,0,0,0,0},lhs}, out{res} {} void operator()(int b) { out = AddB(out, Lut[b]); Lut[1] = LSH(Lut[1]); } bits Lut[2]; bits &out; }; auto MulB = [](auto &&a, auto &&b) { bits res{0,0,0,0,0,0,0,0}; for_each(rbegin(b), rend(b), mul_b{a, res}); return res; }; int main() { cout<<"Identity(0) = "< 0 0 0 1 0 1 0 1\n"; cout << "+ 29 ==> 0 0 0 1 1 1 0 1\n"; cout << "===== =================\n"; auto res = AddB(bits{0,0,0,1,0,1,0,1}, bits{0,0,0,1,1,1,0,1}); cout << " 50 ==> "; Print(res); cout << " 2 ==> 0 0 0 0 0 0 1 0\n"; cout << "+ 250 ==> 1 1 1 1 1 0 1 0\n"; cout << "====== =================\n"; res = AddB(bits{0,0,0,0,0,0,1,0}, bits{1,1,1,1,1,0,1,0}); cout << " 252 ==> "; Print(res); cout << "Subtraction: \n\n"; cout << " 250 ==> 1 1 1 1 1 0 1 0\n"; cout << "- 250 ==> 1 1 1 1 1 0 1 0\n"; cout << "====== =================\n"; res = SubB(bits{1,1,1,1,1,0,1,0}, bits{1,1,1,1,1,0,1,0}); cout << " 0 ==> "; Print(res); cout << " 179 ==> 1 0 1 1 0 0 1 1\n"; cout << "- 111 ==> 0 1 1 0 1 1 1 1\n"; cout << "====== =================\n"; res = SubB(bits{1,0,1,1,0,0,1,1}, bits{0,1,1,0,1,1,1,1}); cout << " 68 ==> "; Print(res); cout << "Multiplication: \n\n"; cout << " 7 ==> 0 0 0 0 0 1 1 1\n"; cout << "x 23 ==> 0 0 0 1 0 1 1 1\n"; cout << "====== =================\n"; res = MulB(bits{0,0,0,0,0,1,1,1}, bits{0,0,0,1,0,1,1,1}); cout << " 161 ==> "; Print(res); cout << " 9 ==> 0 0 0 0 1 0 0 1\n"; cout << "x 28 ==> 0 0 0 1 1 1 0 0\n"; cout << "====== =================\n"; res = MulB(bits{0,0,0,0,1,0,0,1}, bits{0,0,0,1,1,1,0,0}); cout << " 252 ==> "; Print(res); }

[Challenge] Binary Operations.cpp