Take the 2-minute tour ×

I am working on assignment where I will be taking input in binary and will be storing the reverse of it in another address. I am working with a 4-bit word until I am able to get the logic down and then can expand it to a 16-bit word once everything is working.

For example: 1010100101001011 ==> 1101001010010101

Here is my methodology so far:

word: 1010 mask: 0001 result: 0000

1) 1010 & 0001 - AND this together

 result is: 0000 

(I want to only be able to store the least significant bit as the most significant in my result)

2) 1010 & 0010 - Incremented my mask, and ANDing it together with my word

result is: 0010

now I would take the bit in the 2's place, and store that in the 4's place in my result register.

This is where I am having the issues on trying to come up with the logic to isolate the one bit and then store it in another location.

Any tips or advice would be greatly appreciated.

share|improve this question
You want to do a complete bit reversal of a 16 bit word ? You should probably give an input/output example to be clear about this, e.g. 1011001011100011 => 1100011101001101, if I understand the question correctly ? –  Paul R Oct 28 '12 at 21:18
Yes you are correct. I will be using a mask to move through the word and using the AND function to look at an isolated bit position. What I am struggling with is coming up with the logic or figuring out a way to store this into my result register. I would need to figure out how to just send over a single bit in a specific position from the result of me ANDing my word with my mask and then storing that into my result register: bit0 -> bit15, bit1 -> bit 14, etc. –  Mike Oct 28 '12 at 21:28

2 Answers 2

Assuming you mean the minimal LC-3, which does not have a shift or divide instruction:

  • ADD can be used to shift the mask left
  • ADD can be used to shift the result left
  • you can test whether the AND of the mask and the input is zero or not
  • use the result of the test to ADD a 0 or 1 to the result after shifting it left

Here a C rendition

uint16_t reverse16 (uint16_t input)
    uint16_t result = 0u;
    uint16_t mask = 1u;
    int i;

        result = result + result;
        if (0u != (input & mask))
            result += 1u;
        mask = mask + mask;
    return result;

The bithacks site has lots of interesting approaches to this and other bit level problems.

share|improve this answer

Here is the logic in C for a naïve (but easy to understand) implementation of bit reversal of a 16 bit word:

uint16_t w = 0xb2e3;         // our 16 bit word
uint16_t mask0 = 0x0001;     // mask for LS bit
uint16_t mask1 = 0x8000;     // mask for MS bit
uint16_t shift = 15;         // distance between high and low bit positions

for (int b = 0; b < 8; ++b)  // for each pair of low/high bits
    uint16_t b0 = w & mask0; // get low bit
    uint16_t b1 = w & mask1; // get high bit
    w &= ~(mask0 | mask1);   // clear low/high bit in word
    b0 <<= shift;            // swap bit positions
    b1 >>= shift;
    w |= (b0 | b1);          // insert swapped bits back into word
    mask0 <<= 1;             // update masks for next pair of bits
    mask1 >>= 1;
    shift -= 2;              // update distance for next pair of bits 

printf("%#x\n", w);          // w should now contain 0xc74d

Test code: http://ideone.com/GgbzHw

It should be reasonably straightforward to translate the above loop into LC3, although synthesizing |, << and >> may be challenging, given the very limited instruction set.

share|improve this answer
Thank you so much for taking the time to look this up and provide me with the useful information. I have been looking into branches and how they work. Correct me if I am wrong, but this is how I see this working. For example: AND R3, R2, R1 (insert new line here) BRz #1 BRp #2 Now will the first BR statement take a look at the result from the previous line and if it is false it will move to the next line? Or will I have to split up my branch statements? –  Mike Oct 28 '12 at 23:49
There's a good example of how to implement a for loop here: cs.colostate.edu/~fsieker/misc/CtoLC3.html - it uses BRzp for the loop test branch. You might be able to do something simpler for the case where you are just iterating 8 times as above though. –  Paul R Oct 29 '12 at 8:39

Your Answer


