3051

Shift Right Logical from just ADD and NAND?

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.

Recommend

  • Writing into fixed size Buffers in Golang with offsets
  • Detect object with openCV and python
  • Using numpy and pil to convert 565(16bit-color) to 888(24bit-color)
  • Convert Data to DispatchData in Swift 4
  • How can I fill out void* C pointer in Go?
  • group values in intervals
  • Any debug tool in opera (like firebug in firefox)?
  • SQLite callback efficient solution
  • PHP + MySQL - Autocomplete from database not getting data from table
  • Application.AddMessageFilter - how to read exactly what keys were pushed?
  • Getting the parameterised type of a generic in swift?
  • wxPython: binding wx.EVT_CHAR_HOOK disables TextCtrl backspace
  • Reaping zombie process - child
  • Java, will (low + high) >>> 1 overflow?
  • finding a function with particular name
  • Grid creating extra spacing that I don't want
  • Perl function name clash
  • iOS - Is this a task for enums?
  • How to format code on aptana 3?
  • Count New Lines in Text File
  • Is there a parser equivalent of 'fragment' marking in ANTLR4?
  • C++ Single function pointer for all template instances
  • Plotting densities in R
  • Detecting null parameter in preprocessor macro
  • How to read piped content in C?
  • Simple linked list-C
  • std::remove_copy_if_ valgrind bytes in block are possibly lost in loss record
  • Appending Character to Character Array In C
  • Ajax calls do not work in IE unless you fiddle with security settings
  • Parsing a CSV string while ignoring commas inside the individual columns
  • Avoid links criss cross / overlap in d3.js using force layout
  • AES padding and writing the ciphertext to a disk file
  • How to add a column to a Pandas dataframe made of arrays of the n-preceding values of another column
  • Convert array of 8 bytes to signed long in C++
  • Linker errors when using intrinsic function via function pointer
  • LevelDB C iterator
  • Observable and ngFor in Angular 2
  • How to Embed XSL into XML
  • UserPrincipal.Current returns apppool on IIS
  • Conditional In-Line CSS for IE and Others?