Is it possible to implement bitwise operators using integer arithmetic?

Question

I ran into a rather peculiar problem. I am working on a compiler for an architecture that does not support bitwise operations. However, it handles the signed 16-bit integer arithmetic, and I was wondering if it is possible to implement bitwise operations using only:

• Addition (c = a + b)
• Subtraction (c = a - b)
• Department (c = a / b)
• Multiplication (c = a * b)
• Module (c = a% b)
• Minimum (c = min (a, b))
• Maximum (c = max (a, b))
• Comparison (c = (a <b), c = (a == b), c = (a <= b), et.c.)
• Transitions (goto, for, et.c.)

Bitwise operations that I want to support:

• Or (c = a | b)
• And (c = a and b)
• Xor (c = a ^ b)
• Left shift (c = a <b)
• Right shift (c = a → b)
  • (All integers are signed, so this is a problem)
• Signed shift (c = a →> b)
• One addition (a = ~ b)
  • (solution already found, see below)

Usually the problem is the opposite; how to achieve arithmetic optimization using bitwise hacks. However, not in this case.

Writable memory is very scarce in this architecture, therefore, bitwise operation is required. Bitwise functions themselves should not use many temporary variables. However, read-only persistent data and memory commands are plentiful. Also note that jumps and branches are not expensive, and all data is easily cached. Jumps cost half a cycle, as arithmetic instructions do (including loading / storing). In other words, all of the above supported functions cost twice as many cycles of one jump.

Some thoughts that may help:

---

I realized that you can make one addition (negation of bits) with the following code:

// Bitwise one complement b = ~a; // Arithmetic one complement b = -1 - a; 

I also remember the old cracked shift when dividing with a power of two, so the bitwise shift can be expressed as:

 // Bitwise left shift b = a << 4; // Arithmetic left shift b = a * 16; // 2^4 = 16 // Signed right shift b = a >>> 4; // Arithmetic right shift b = a / 16; 

For the remaining bitwise operations, I do not know a bit. I want the architects of this architecture to provide bit operations.

I would also like to know if there is a quick / easy way to calculate the power of two (for shift operations) without using a memory data table. A naive solution would be to go to the multiplication field:

 b = 1; switch (a) { case 15: b = b * 2; case 14: b = b * 2; // ... exploting fallthrough (instruction memory is magnitudes larger) case 2: b = b * 2; case 1: b = b * 2; } 

Or the Set and Jump approach:

 switch (a) { case 15: b = 32768; break; case 14: b = 16384; break; // ... exploiting the fact that a jump is faster than one additional mul // at the cost of doubling the instruction memory footprint. case 2: b = 4; break; case 1: b = 2; break; } 

Answer 1

The first solutions for the shift (the shift is the distance of the shift, should not be negative, but the operand, which should be shifted and also contains the result when this is done). The power table is used by all three shift operations.

 // table used for shift operations powtab = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, -32768 }; // logical shift left if (shift > 15) { a = 0; // if shifting more than 15 bits to the left, value is always zero } else { a *= powtab[shift]; } // logical shift right (unsigned) if (shift > 15) { a = 0; // more than 15, becomes zero } else if (shift > 0) { if (a < 0) { // deal with the sign bit (15) a += -32768; a /= powtab[shift]; a += powtab[15 - shift]; } else { a /= powtab[shift]; } } // arithmetic shift right (signed) if (shift >= 15) { if (a < 0) { a = -1; } else { a = 0; } } else if (shift > 0) { if (a < 0) { // deal with the sign bit a += -32768; a /= powtab[shift]; a -= powtab[15 - shift]; } else { // same as unsigned shift a /= powtab[shift]; } } 

For AND, OR and XOR, I could not find a simple solution, so I will do this with a loop for each individual bit. Maybe the best trick for this. Pseudocode assumes that a and b are input operands, c is the value of the result, x is the loop counter (each loop must be executed exactly 16 times):

 // XOR (^) c = 0; for (x = 0; x <= 15; ++x) { c += c; if (a < 0) { if (b >= 0) { c += 1; } } else if (b < 0) { c += 1; } a += a; b += b; } // AND (&) c = 0; for (x = 0; x <= 15; ++x) { c += c; if (a < 0) { if (b < 0) { c += 1; } } a += a; b += b; } // OR (|) c = 0; for (x = 0; x <= 15; ++x) { c += c; if (a < 0) { c += 1; } else if (b < 0) { c += 1; } a += a; b += b; } 

It is assumed that all variables are 16 bits, and all operations behave as signed (therefore a <0 is actually true when bit 15 is set).

EDIT: I really tested all possible operand values ​​(-32768 to 32767) for offsets ranging from 0 to 31 for correctness and works correctly (assuming that the integer divisions). For the AND / OR / XOR code, an exhaustive test takes too much time on my machine, but since the code for them is quite simple, there should be no cases with an edge in any case.

Answer 2

In this environment, it would be better if you could actually configure the use of arithmetic operators to clear the components of integers.

eg.

 if (a & 16) becomes if ((a % 32) > 15) a &= 16 becomes if ((a % 32) < 15) a += 16 

The conversions for these operators are fairly obvious if you limit RHS to a constant power of 2.

Flaking two or four bits is also easy to do.

Answer 3

Incomplete answer to the old question, here the main focus is on AND, OR, XOR. Once a solution is found for one of these bitwise operations, the other two can be obtained. There are several ways, one of which is shown in the following test program (compiled in gcc version 4.6.3 (Ubuntu / Linaro 4.6.3-1ubuntu5)).

In December 2018, I discovered a mistake in the solution. The XOR commented below works only because the intermediate results in a+b-2*AND(a,b) translated into int , which is more than 16 bits for all modern compilers.

 #include <stdint.h> #include <stdio.h> #include <stdlib.h> //#define XOR(a,b) (a + b - 2*AND(a,b)) // Error. Intermediate overflow #define XOR(a,b) (a - AND(a,b) + b - AND(a,b) ) #define IOR(a,b) XOR(XOR(a,b),AND(a,b)) // Credit to Jan Gray, Gray Research LLC, for IOR static const uint16_t andlookup[256] = { #define C4(a,b) ((a)&(b)), ((a)&(b+1)), ((a)&(b+2)), ((a)&(b+3)) #define L(a) C4(a,0), C4(a,4), C4(a,8), C4(a,12) #define L4(a) L(a), L(a+1), L(a+2), L(a+3) L4(0), L4(4), L4(8), L4(12) #undef C4 #undef L #undef L4 }; uint16_t AND(uint16_t a, uint16_t b) { uint16_t r=0, i; for ( i = 0; i < 16; i += 4 ) { r = r/16 + andlookup[(a%16)*16+(b%16)]*4096; a /= 16; b /= 16; } return r; } int main( void ) { uint16_t a = 0, b = 0; do { do { if ( AND(a,b) != (a&b) ) return printf( "AND error\n" ); if ( IOR(a,b) != (a|b) ) return printf( "IOR error\n" ); if ( XOR(a,b) != (a^b) ) return printf( "XOR error\n" ); } while ( ++b != 0 ); if ( (a & 0xff) == 0 ) fprintf( stderr, "." ); } while ( ++a != 0 ); return 0; } 

Answer 4

You can work in stages (as Mark Byers suggested) by adding every bit that will be slow.

Or you can speed up the process and use 2d lookup tables, which store the results for, say, two 4-bit operands and work with them. You will need fewer selections than if you were working on bits.

You can also do everything by adding, subtracting and> = operations. Each bitwise operation can be expanded into something like this with macros:

 /*I didn't actually compile/test it, it is just illustration for the idea*/ uint16 and(uint16 a, uint16 b){ uint16 result = 0; #define AND_MACRO(c) \ if (a >= c){ \ if (b >= c){\ result += c;\ b -= c;\ }\ a -= c;\ }\ else if (b >= c)\ b -= c; AND_MACRO(0x8000) AND_MACRO(0x4000) AND_MACRO(0x2000) AND_MACRO(0x1000) AND_MACRO(0x0800) AND_MACRO(0x0400) AND_MACRO(0x0200) AND_MACRO(0x0100) AND_MACRO(0x0080) AND_MACRO(0x0040) AND_MACRO(0x0020) AND_MACRO(0x0010) AND_MACRO(0x0008) AND_MACRO(0x0004) AND_MACRO(0x0002) AND_MACRO(0x0001) #undef AND_MACRO return result; } 

To implement this, 3 variables are required.

Each bitwise operation will revolve around macros similar to AND_MACRO - you compare the remaining values ​​of a and b with a "mask" (which is the parameter "c"). then add a mask to the result in the if branch suitable for your operation. And you subtract the mask from the values ​​if the bit is set.

Depending on your platform, this may be faster than extracting each bit using% and / and then returning it using multiplication.

See for yourself, whichever is best for you.

Answer 5

As long as you want it to be very expensive, yes.

Basically, you explicitly put a number in the base-2 representation. You do this the same way you would put a number in base-10 (for example, to print it), i.e. by re-dividing it.

This turns your number into a bools array (or int in the range of 0.1), then we add functions to work with these arrays.

not that it is significantly more expensive than bitwise operations, and that almost any architecture will supply bitwise operators.

In C (of course, in C you have bitwise operators, but ...) the implementation could be:

 include <limits.h> const int BITWIDTH = CHAR_BIT; typedef int[BITWIDTH] bitpattern; // fill bitpattern with base-2 representation of n // we used an lsb-first (little-endian) representation void base2(char n, bitpattern array) { for( int i = 0 ; i < BITWIDTH ; ++i ) { array[i] = n % 2 ; n /= 2 ; } } void bitand( bitpattern op1, bitpattern op2, bitpattern result ) { for( int i = 0 ; i < BITWIDTH ; ++i ) { result[i] = op1[i] * op2[i]; } } void bitor( bitpattern op1, bitpattern op2, bitpattern result ) { for( int i = 0 ; i < BITWIDTH ; ++i ) { result[i] = (op1[i] + op2[i] != 0 ); } } // assumes compiler-supplied bool to int conversion void bitxor( bitpattern op1, bitpattern op2, bitpattern result ) { for( int i = 0 ; i < BITWIDTH ; ++i ) { result[i] = op1[i] != op2[i] ; } } 

Answer 6

Just two other approaches

For example 16 bits and :

 int and(int a, int b) { int d=0x8000; int result=0; while (d>0) { if (a>=d && b>=d) result+=d; if (a>=d) a-=d; if (b>=d) b-=d; d/=2; } return result; } 

Here's a fun 2-bit and no loops or lookup table:

 int and(int a, int b) { double x=a*b/12; return (int) (4*(sign(ceil(tan(50*x)))/6+x)); }