Recursively reversing bits in assembly language

Question

Given a sequence of 16 bits, I want to recursively reverse these bits.
For example, 1001 1110 0010 0110 becomes 0110 0100 0111 1001.

I only have access to ADD, AND and NOT.
The subroutine accepts 2 parameters, the number of bits remaining to be reversed and the bit values. It returns the result.

I'm trying to think of ways to do this. One thing that's popped into my head is having a sequence of bits : 0000 0000 0000 0001 to start, and adding it with itself the number of bits left to be processed left -1 times, then anding these bits with the passed in bit pattern. The problem is this seems very ineficient, and also I'm not sure how I would store the result to reverse the bits.

Any hints on this? It is homework, so just hints please :)

I'm assuming you're allowed to use some kinds of jumps as well? What about MOV and CMP and TEST? — user470379
Yup. Jumps, branches, that sort of thing. I don't have any of those. However, when I use ADD, AND or NOT, 3 condition codes are set, Negative, Zero and Positive. I can use those to determine where I want to branch. I don't have MOV CMP or TEST though. — Justin

Chris Dodd Chris Dodd · Accepted Answer · 2011-03-21T05:09:30

You've already figured out you can use ADD to shift left (adding a value to itself). So you can repeatedly shift and then AND with a constant with 1 high bit set to extract the bits from highest to lowest. You can build OR out of AND and NOT (via DeMorgan's law), so you can recombine those bits from lowest to highest by or-ing together single bits starting with a constant 1 and shifting that left as you go, which will give you the reversed bit sequence.

Turning that into a recursive process is fairly straight-forward

Recursively reversing bits in assembly language

1 Answers