Question:

I'm making a multiplier in a very simple assembly language in which I have BEQ, NAND, and ADD to create a SRL. I also have to keep the multiplier under 50 lines (16 used thus far) so hopefully the solution can be thrown in a loop.

EDIT: My question is how can I implement an SRL with just a NAND and an ADD

Had an idea although it is very inefficient, maybe someone can improve it:

Decrement say, a, by 1. Store that value in b. Add b and b and store in c. Beq c with a, if it's true then b is half of a, aka srl. Only problem is it would have to loop thousands of times in some cases. Still open to other ideas.

Answer1:You don't really need a right shift to implement multiplication. See how this can be done, sample code in C:

```
#include <stdio.h>
typedef unsigned char uint8;
typedef unsigned short uint16;
uint16 Mul8x8(uint8 a, uint8 b)
{
int cnt;
uint16 prod = 0;
for (cnt = 8; cnt > 0; cnt--)
{
prod += prod;
if (a & 0x80)
prod += b;
a += a;
}
return prod;
}
const uint8 Multipliers[][2] =
{
{ 0x00, 0x01 },
{ 0x01, 0x00 },
{ 0x33, 0x10 },
{ 0x11, 0x0C },
{ 0x0F, 0x0F },
{ 0x80, 0x80 },
{ 0xFF, 0xFF },
};
int main(void)
{
int i;
for (i = 0; i < sizeof(Multipliers) / sizeof(Multipliers[0]); i++)
{
uint8 a = Multipliers[i][0];
uint8 b = Multipliers[i][1];
uint16 p = a * b;
uint16 p2 = Mul8x8(a, b);
printf("0x%02X * 0x%02X = 0x%04X %c= 0x%04X\n",
a, b, p, "!="[p == p2], p2);
}
return 0;
}
```

Output ([ideone])(<a href="http://ideone.com/NwsykN" rel="nofollow">http://ideone.com/NwsykN</a>)):

```
0x00 * 0x01 = 0x0000 == 0x0000
0x01 * 0x00 = 0x0000 == 0x0000
0x33 * 0x10 = 0x0330 == 0x0330
0x11 * 0x0C = 0x00CC == 0x00CC
0x0F * 0x0F = 0x00E1 == 0x00E1
0x80 * 0x80 = 0x4000 == 0x4000
0xFF * 0xFF = 0xFE01 == 0xFE01
```

Answer2:Here is a code that uses only the operations you have (you need 2 NANDs for AND and BEQ around jump for BNE).

If you <em>really</em> need right shift, you can use the same kind of loop with test and set instead of shift and add. It will take N-1 iterations to shift N bits.

```
#include <stdio.h>
unsigned mult(unsigned x, unsigned y)
{
unsigned test = 1, ans = 0;
next:
if ((test & x) == 0) goto skip;
ans += y;
skip:
y += y;
test += test;
if (test != 0) goto next;
return ans;
}
int main(void)
{
unsigned x, y;
while (1) {
printf("Operands: ");
if (scanf("%u%u", &x, &y) != 2) break;
printf("Result: %u\n", mult(x, y));
}
return 0;
}
```

Answer3:Right shift can be accomplished by two bit masks: `out_bit=1`

, `in_bit=1<<RSHIFT`

by copying bits addressed by in_bit mask to the position addressed by out_bit mask -- just like one would shift arrays of bytes.

```
while (in_bit > 0) {
if (word & in_bit) out_word+=out_bit;
in_bit+=in_bit; out_bit+=out_bit;
}
```

To operate with NAND, ie. `~(a & b)`

, there's an option to

```
do {
if (~(word & in_bit) == -1) {
out_word+=out_bit;
}
in_bit+=in_bit; out_bit+=out_bit;
} while (!(in_bit==0));
```

Now there are just operators ADD / NAND.

Answer4:In order to implement <strong>multiplier</strong>, you need <strong>logical shift left</strong>, not shift right. Shift left is simply multiplying by 2. It can be implemented by adding the value by itself:

```
a = a + a ; this will produce the value shifted left.
```

Shifting right is not so obvious though.