Implement bit operations only by ADD, SUB, MUL and DIV instructions

I am writing a compiler -- just for fun and to improve my skills. I'd like to implement a subset of C language. The problem is: I'm compiling to the assembler of theoretical 16-bit RISC processor called Sextium II (we used to teach assembler on it on our University).

The processor uses only 16 commands, and none of them is a bit operation. I would like to implement C bit operators -- and afterwards half-precision floats -- but I have no idea开发者_开发问答 how to implement bit operations using only ADD, SUB, MUL and DIV instructions. Bit-shift is quite easy, it is just multiplication or division by 2^n, where n is the shift length. But what about AND, OR, NOT or XOR?

EDIT To be clear: processor computes only in 16-bit signed U2 arithmetics.

Well if you look at a bitwise truth table for add for example:

a b  c r
0 0  0 0
0 1  0 1
1 0  0 1
1 1  1 0

a and b are the input operands r is the result c is the carry out.

From a bitwise perspective an add is an xor. But to use this as a generic xor you would need to perform 16 add operations, one for each bit plus all the work that surrounds masking one operand and extracting the result bit.

a b  c r
0 1  0 1
1 1  1 0

Focusing in on the add again but with the b operand always a one, you get a not function. Here again, would need masking and shifting.

of course you dont have masking and shifting do you?

A multiplier will shift left, times 2 is a shift of 1 times 4 a shift of 2 and so on. Likewise a divide is a shift right. Divide by 4 is a shift of 2, divide by 8 is a shift of 3 and so on. You could mask individual bits this way, divide by 8 to shift right 3 then multiply by 0x8000 to shift left 15, then divide by 0x1000. Would that be the same as anding with a 0x0008?

If that works then you could say multiply by 0x100 then divide by 0x100 and have that be the same as anding with 0xFF00.

is it a signed multiply (and divide) or unsigned? or do you have both?