Binary Right Shift, Given Only Addition

Question

I am working on a project where I am reading memory locations and need to output their hex value in ASCII.

The language gives me a 16 bit word length, so I have a need to divide to grab a nibble at a time to convert to hex. Unfortunately, the language only offers and, or, not, and add for mathematical/logical functions.

I've figured I can create the desired effect by left shifting and testing for a negative flag to add a 1 to the end after shifting, but I'm figuring there has to be a better method for doing this.

Any insight would be appreciated.

Answer 1

Do you have an add with carry? Instead of the test for negative add the bit off the end and add a zero with carry to put it back on the right. doesnt really save much. So far I cant think of another solution, shift left, test a bit, if set add 1 to something and shift that something:

uint a,b,i;

b=0;
for(i=0;i<4;i++)
{
   b=b+b;
   if(a&0x8000) b+=1;
   a=a+a;
}

If uint above was 16 bits then the above would give you a right shift of 12. a would be destroyed in the process to create b, as written.

Answer 2

Using AND you can set all bits to zero except the last significant nibble:

0101010111010101
0000000000001111 AND
----------------
0000000000000101

By shifting the whole thing right, you can read the next nibble:

0101010111010101 SHR 4
----------------
    010101011101
0000000000001111 AND
----------------
0000000000001101

Is that of any use to you?

Answer 3

You can try it in reverse: instead of trying to implement the right shift, you can use brute force. Here is an example for highest nibble:

unsigned rez, tmp;
for (rez = 0, tmp = some_word & 0x0FFF; tmp != some_word; rez++, tmp += 0x1000);

Answer 4

So the original method I used worked. I also came up with another, incase anyone ever has this problem again.

I built a subroutine that evaluates 4 bits at a time and creates a number based on the evaluation, for some C style pseudo code it looks like this:

16bitSignedInt bin; //binary being analyzed
int value; //number being built

for (int i = 0; i < 4; i++) // while 0-3, for each nibble of the 16 bits
{
   if (bin.bit15 = 1)
      value += 8; // dominate bit in nibble

   bin <<= 1; // left shift 1

   if (bin.bit15 = 1)
      value += 4; // 2nd bit in nibble

   bin <<= 1; // left shift 1

   if (bin.bit15 = 1)
      value += 2; // 3rd bit in nibble

   bin <<= 1; // left shift 1

   if (bin.bit15 = 1)
      value += 1; // last bit in nibble

   bin <<= 1; // left shift 1

   //do work with value
}

Crude, but effective.