how to add 2 numbers without using + and bitwise operators?
+1
A:
Might I ask why you need to do this? You HAVE to use some sort of addition operator/bitwise operator as far as I know... or I guess instead of doing a+b you can write a - (b*-1) .. although that makes no sense at all.
ItzWarty
2010-02-21 18:10:45
Most languages I've used have a unary `-` operator, so `a - (-b)` will work.
Carl Norum
2010-02-21 18:12:37
+2
A:
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.
#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);
}
}
Deadcode
2010-02-22 16:43:21