StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here you go, addition and subtraction in C++ using nothing but comparison and logical operators. I didn't even use array indexing, because that would require implicit pointer arithmetic — and allowing pointer arithmetic would trivialize this.</p> <pre><code>#include <iostream> #include <iomanip> #include <ctime> using namespace std; typedef unsigned char byte; enum { LITTLE_ENDIAN, BIG_ENDIAN, } endianness; union dword_union { long dword; struct { byte byte0; byte byte1; byte byte2; byte byte3; } bytes; }; struct byte_bits { bool bit0; bool bit1; bool bit2; bool bit3; bool bit4; bool bit5; bool bit6; bool bit7; }; struct dword_bytes { byte_bits byte0; byte_bits byte1; byte_bits byte2; byte_bits byte3; }; void init_endianness() { dword_union db; db.bytes.byte0=1; db.bytes.byte1=2; db.bytes.byte2=3; db.bytes.byte3=4; {{}} if (db.dword == 0x04030201) endianness = LITTLE_ENDIAN; else if (db.dword == 0x01020304) endianness = BIG_ENDIAN; else throw "Unknown endianness"; } #define R(a,b) (x>=a && x<=b) void byte_to_bits(byte_bits &bits, byte x) { bits.bit0 = R(1,1)||R(3,3)||R(5,5)||R(7,7)||R(9,9)||R(11,11)||R(13,13)||R(15,15)||R(17,17)||R(19,19)||R(21,21)||R(23,23)||R(25,25)||R(27,27)||R(29,29)||R(31,31)||R(33,33)||R(35,35)||R(37,37)||R(39,39)||R(41,41)||R(43,43)||R(45,45)||R(47,47)||R(49,49)||R(51,51)||R(53,53)||R(55,55)||R(57,57)||R(59,59)||R(61,61)||R(63,63)||R(65,65)||R(67,67)||R(69,69)||R(71,71)||R(73,73)||R(75,75)||R(77,77)||R(79,79)||R(81,81)||R(83,83)||R(85,85)||R(87,87)||R(89,89)||R(91,91)||R(93,93)||R(95,95)||R(97,97)||R(99,99)||R(101,101)||R(103,103)||R(105,105)||R(107,107)||R(109,109)||R(111,111)||R(113,113)||R(115,115)||R(117,117)||R(119,119)||R(121,121)||R(123,123)||R(125,125)||R(127,127)||R(129,129)||R(131,131)||R(133,133)||R(135,135)||R(137,137)||R(139,139)||R(141,141)||R(143,143)||R(145,145)||R(147,147)||R(149,149)||R(151,151)||R(153,153)||R(155,155)||R(157,157)||R(159,159)||R(161,161)||R(163,163)||R(165,165)||R(167,167)||R(169,169)||R(171,171)||R(173,173)||R(175,175)||R(177,177)||R(179,179)||R(181,181)||R(183,183)||R(185,185)||R(187,187)||R(189,189)||R(191,191)||R(193,193)||R(195,195)||R(197,197)||R(199,199)||R(201,201)||R(203,203)||R(205,205)||R(207,207)||R(209,209)||R(211,211)||R(213,213)||R(215,215)||R(217,217)||R(219,219)||R(221,221)||R(223,223)||R(225,225)||R(227,227)||R(229,229)||R(231,231)||R(233,233)||R(235,235)||R(237,237)||R(239,239)||R(241,241)||R(243,243)||R(245,245)||R(247,247)||R(249,249)||R(251,251)||R(253,253)||R(255,255); bits.bit1 = R(2,3)||R(6,7)||R(10,11)||R(14,15)||R(18,19)||R(22,23)||R(26,27)||R(30,31)||R(34,35)||R(38,39)||R(42,43)||R(46,47)||R(50,51)||R(54,55)||R(58,59)||R(62,63)||R(66,67)||R(70,71)||R(74,75)||R(78,79)||R(82,83)||R(86,87)||R(90,91)||R(94,95)||R(98,99)||R(102,103)||R(106,107)||R(110,111)||R(114,115)||R(118,119)||R(122,123)||R(126,127)||R(130,131)||R(134,135)||R(138,139)||R(142,143)||R(146,147)||R(150,151)||R(154,155)||R(158,159)||R(162,163)||R(166,167)||R(170,171)||R(174,175)||R(178,179)||R(182,183)||R(186,187)||R(190,191)||R(194,195)||R(198,199)||R(202,203)||R(206,207)||R(210,211)||R(214,215)||R(218,219)||R(222,223)||R(226,227)||R(230,231)||R(234,235)||R(238,239)||R(242,243)||R(246,247)||R(250,251)||R(254,255); bits.bit2 = R(4,7)||R(12,15)||R(20,23)||R(28,31)||R(36,39)||R(44,47)||R(52,55)||R(60,63)||R(68,71)||R(76,79)||R(84,87)||R(92,95)||R(100,103)||R(108,111)||R(116,119)||R(124,127)||R(132,135)||R(140,143)||R(148,151)||R(156,159)||R(164,167)||R(172,175)||R(180,183)||R(188,191)||R(196,199)||R(204,207)||R(212,215)||R(220,223)||R(228,231)||R(236,239)||R(244,247)||R(252,255); bits.bit3 = R(8,15)||R(24,31)||R(40,47)||R(56,63)||R(72,79)||R(88,95)||R(104,111)||R(120,127)||R(136,143)||R(152,159)||R(168,175)||R(184,191)||R(200,207)||R(216,223)||R(232,239)||R(248,255); bits.bit4 = R(16,31)||R(48,63)||R(80,95)||R(112,127)||R(144,159)||R(176,191)||R(208,223)||R(240,255); bits.bit5 = R(32,63)||R(96,127)||R(160,191)||R(224,255); bits.bit6 = R(64,127)||R(192,255); bits.bit7 = R(128,255); } long random_dword() { return rand() + (rand()<<15) + (rand()<<30); } void byte_not(byte_bits &a, const byte_bits &x) { a.bit0 = !x.bit0; a.bit1 = !x.bit1; a.bit2 = !x.bit2; a.bit3 = !x.bit3; a.bit4 = !x.bit4; a.bit5 = !x.bit5; a.bit6 = !x.bit6; a.bit7 = !x.bit7; } void byte_and(byte_bits &a, const byte_bits &x, const byte_bits &y) { a.bit0 = x.bit0 && y.bit0; a.bit1 = x.bit1 && y.bit1; a.bit2 = x.bit2 && y.bit2; a.bit3 = x.bit3 && y.bit3; a.bit4 = x.bit4 && y.bit4; a.bit5 = x.bit5 && y.bit5; a.bit6 = x.bit6 && y.bit6; a.bit7 = x.bit7 && y.bit7; } void byte_xor(byte_bits &a, const byte_bits &x, const byte_bits &y) { a.bit0 = x.bit0 != y.bit0; a.bit1 = x.bit1 != y.bit1; a.bit2 = x.bit2 != y.bit2; a.bit3 = x.bit3 != y.bit3; a.bit4 = x.bit4 != y.bit4; a.bit5 = x.bit5 != y.bit5; a.bit6 = x.bit6 != y.bit6; a.bit7 = x.bit7 != y.bit7; } bool byte_nonzero(const byte_bits &x) { return x.bit0 || x.bit1 || x.bit2 || x.bit3 || x.bit4 || x.bit5 || x.bit6 || x.bit7; } class bit_int { public: bit_int() {} bit_int(const dword_bytes &x) { bytes = x; } bit_int(const bit_int &x) { bytes = x.bytes; } bit_int(long x) { dword_union db; db.dword = x; if (endianness==LITTLE_ENDIAN) { byte_to_bits(bytes.byte0, db.bytes.byte0); byte_to_bits(bytes.byte1, db.bytes.byte1); byte_to_bits(bytes.byte2, db.bytes.byte2); byte_to_bits(bytes.byte3, db.bytes.byte3); } else { byte_to_bits(bytes.byte0, db.bytes.byte3); byte_to_bits(bytes.byte1, db.bytes.byte2); byte_to_bits(bytes.byte2, db.bytes.byte1); byte_to_bits(bytes.byte3, db.bytes.byte0); } } bit_int operator~() const { bit_int copy; byte_not(copy.bytes.byte0, bytes.byte0); byte_not(copy.bytes.byte1, bytes.byte1); byte_not(copy.bytes.byte2, bytes.byte2); byte_not(copy.bytes.byte3, bytes.byte3); return copy; } bit_int operator&(const bit_int &y) const { bit_int copy; byte_and(copy.bytes.byte0, bytes.byte0, y.bytes.byte0); byte_and(copy.bytes.byte1, bytes.byte1, y.bytes.byte1); byte_and(copy.bytes.byte2, bytes.byte2, y.bytes.byte2); byte_and(copy.bytes.byte3, bytes.byte3, y.bytes.byte3); return copy; } bit_int operator^(const bit_int &y) const { bit_int copy; byte_xor(copy.bytes.byte0, bytes.byte0, y.bytes.byte0); byte_xor(copy.bytes.byte1, bytes.byte1, y.bytes.byte1); byte_xor(copy.bytes.byte2, bytes.byte2, y.bytes.byte2); byte_xor(copy.bytes.byte3, bytes.byte3, y.bytes.byte3); return copy; } bit_int lshift() const { bit_int copy; copy.shifter.shifted = bytes; copy.bytes.byte0.bit0 = 0; return copy; } operator bool() const { return byte_nonzero(bytes.byte0) || byte_nonzero(bytes.byte1) || byte_nonzero(bytes.byte2) || byte_nonzero(bytes.byte3); return true; } bit_int operator+(const bit_int &addend) { bit_int x = *this; bit_int y = addend; bit_int a, b; do { a = x & y; b = x ^ y; x = b; y = a.lshift(); } while (a); return b; } bit_int operator-(const bit_int &addend) { bit_int x = *this; bit_int y = addend; bit_int a, b; do { a = ~x & y; b = x ^ y; x = b; y = a.lshift(); } while (a); return b; } friend ostream &operator<<(ostream &out, const bit_int &x) { out << x.nibbles.nibble7 << x.nibbles.nibble6 << x.nibbles.nibble5 << x.nibbles.nibble4; out << x.nibbles.nibble3 << x.nibbles.nibble2 << x.nibbles.nibble1 << x.nibbles.nibble0; return out; } private: struct nibble { bool bit0; bool bit1; bool bit2; bool bit3; friend ostream &operator<<(ostream &out, const nibble &a) { return out << (a.bit3 ? a.bit2 ? a.bit1 ? a.bit0 ? 'F' : 'E' : a.bit0 ? 'D' : 'C' : a.bit1 ? a.bit0 ? 'B' : 'A' : a.bit0 ? '9' : '8' : a.bit2 ? a.bit1 ? a.bit0 ? '7' : '6' : a.bit0 ? '5' : '4' : a.bit1 ? a.bit0 ? '3' : '2' : a.bit0 ? '1' : '0'); } }; union { dword_bytes bytes; struct { nibble nibble0; nibble nibble1; nibble nibble2; nibble nibble3; nibble nibble4; nibble nibble5; nibble nibble6; nibble nibble7; } nibbles; struct { bool highbit; dword_bytes shifted; } shifter; }; }; void main() { try { init_endianness(); srand((int)time(NULL)); int x = random_dword(); int y = random_dword(); bit_int a(x); bit_int b(y); cout << "0x" << a << " + " << "0x" << b << " = " << "0x" << (a + b) << endl; cout << "0x" << a << " - " << "0x" << b << " = " << "0x" << (a - b) << endl; } catch (char *error) { printf("Error: %s\n", error); } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload