Looking at individual bits

Question

In MIPS Assembly, is it possible to extract only i-th and j-th bits of a string and then place these individual bits back into their original location.

Consider: 1100

Extract: 2nd and 3rd bits and swap them to get result 1010

Answer 1

Look at the AND truth table result r = a AND b

ab r
00 0
01 0
10 0
11 1

Look at these two cases:

10 0
11 1

anything ANDed with 1 is itself, now these two cases

00 0
01 0

anything ANDed with zero is zero.

with four bits abcd to extract the c bit, knowing these two features of anding, anything anded with zero and anything anded with one.

    abcd
AND 0010
=========
    00c0

we have isolated bit c and we dont care if it is a zero or a one bit we have isolated it. the bits anded with zeros were forced to zero and the bit anded with a 1 was unchanged.

Likewise anding abcd with 0100 gives us 0b00 isolating bit b.

so now we have two intermediate results 0b00 and 00c0. you wanted to swap their positions, shifting will do that, depending on your instruction set (I know you said mips but just follow please) some instruction sets might rotate or shift in the carry bit and some rotate or shift in zeros or arithmetic shifts vs logic shifts may duplicate the most significant bit instead of shift in zeros. So you need to examine what shifting is available in the instruction set you are using and if there isnt a clean shifts in zeros solution then you need to add more operations to clean up any side effects of the shift. In this case we want to move the b bit over one to the right and the c bit over one to the left so the operation you need to find and use is

0b00 >> 1 = 00b0
00c0 << 1 = 0c00

now the bits are in the right bit position we have three things

abcd
0c00
00b0

So we have two truth tables to examine, one is the AND truth table above and we know the anything anded with one, anything anded with zero thing. the other is the OR truth table

ab r
00 0
01 1
10 1
11 1

In particular the first two

00 0
01 1

anything ORed with zero is itself. and note the second two

10 1
11 1

anything ORed with 1 is 1.

How do we use AND and OR to get the bits in place? Well we have two choices anything ORed with zero is itself, the other is anything ANDed with 1 is itself. what we need to do is manipulate the original number abcd and make it either a00d or a11d. That calls into play the other half of the AND and OR tables. Anything anded with 0 is 0, anything orred with 1 is 1. so to turn abcd into a00d we need to and it with 1001

    abcd
AND 1001
=========
    a00d

the a and d anded with one are themselves the b and c anded with 0 are 0

the other choice is

    abcd
OR  0110
=========
    a11d

a and d are ored with 0 so they dont change b and c are orred with 1 so those bit locations become ones

the final step is to take our other intermediate values and mix them in

    a00d
OR  0c00
=========  
    ac0d

    ac0d
OR  00b0
=========  
    acbd

the other choice is more complicated, if we simply did this

    a11d
AND 0c00
========
    0c00

in order to use that identity we would need to modify the 0c00 and make it 1c11

0c00 OR 1011 = 1c11
1c11 AND a11d = ac1d
00b0 OR 1101 = 11b1
11b1 AND ac1d = acbd

In short the conventional solution is to and with ones to isolate, and with zeros to clean out the bit positions and then or in the new values:

abcd AND 0100 = 0b00
abcd AND 0010 = 00c0
0b00 >> 1 = 00b0
00c0 << 1 = 0c00
abcd AND 1001 = a00d
a00d OR 0c00 = ac0d
ac0d OR 00b0 = acbd

In C this would be something like this (and this shows your temporary variables)

//abcd is our original variable
tempb = abcd & 4;
tempc = abcd & 2;
tempb = tempb >> 1;
tempc = tempc << 1;
result = abcd & 9; 
result = result | tempc;
result = result | tempb;
//and finished, result contains the...result.

You already got a complete answer from gusbro, this is half the answer, I assume the task of using the logical operations is half the problem, the other half of the problem is choosing instructions and registers for the instruction set in question (notice how I have solved the problem thus far without needing to specify an instruction set, because at this point we can use any instruction set, it might take more than one instruction per step, but it is generic to this point).

Note this is a four bit solution, you are likely going to be using an instruction set with more than four bits in the registers so you need to know what bits to tack on the left of the operands in these equations to not mess up the other bits.

Another identity that gusbro used which I didnt, is anything XORed with itself is zero. his two xor operations could be implemented with a single and operation with a constant, depending on the instruction set that might take more than one instruction or have additional memory cycles required.

the key to this type of work is understanding these logical identities and applying them. when someone says (mask and shift) mask means anding with a constant that has ones in the bit positions you want to keep, then shifting puts the bit in a particular position, say for example you wanted to take abcd and isolate the c bit in such a way that the result is either a zero or one you would "mask and shift"

abcd AND 0010 = 00c0
00c0 >> 1 = 000c

The and is the mask, the shift is the shift, the result is a 0 if c was a 0 and 1 if c was a 1.

Likewise you can

abcd >> 1 = 0abc
0abc AND 0001 = 000c

shift then mask.

Your homework assignment could be re-arranged as

abcd >> 1 = 0abc
abcd << 1 = bcd0
0abc AND 0010 = 00b0
bcd0 AND 0100 = 0c00
abcd AND 1001 = a00d
00b0 OR 0c00 = 0cb0
a00d OR 0cb0 = acbd

and you can start to see other variations on the theme. and those variations can turn into optimizations depending on the instruction set you are targeting.

Answer 2

You can do it by applying masks and shifts. Assuming your data is stored in a register, to obtain the i-th bit you would apply an AND with the constant 2^i to clear all the bits but the i-th bit. Then you can easily "move" that bit to other position using either a left shift or a right shift.

Now, to swap 2 bits would need a little more fiddling. You might for example, extract the two bits to some registers, clear thos bits from the original register, then shift each of the two registers to locate them in the "swapped" position and finally OR everything.

E.g.:

  li $t0, 12         # Our constant, 1100b, is stored in $t0
  andi $t1, $t0, 2   # Mask the second bit and put it in $t1
  andi $t2, $t0, 4   # Mask the third bit and put it in $t2
  xor $t0, $t0, $t1  # Ensures the second bit $t0 is zero 
  xor $t0, $t0, $t2  # Ensures the third bit $t0 is zero 
  sll $t1, $t1, 1    # Moves $t1 one position to the left (second bit goes to third bit)
  srl $t2, $t2, 1    # Moves $t2 one position to the right (third bit goes to second bit)
  or $t1, $t1, $t2   # now we OR everything
  or $t0, $t0, $t1   # to get the final result, in this case 1010b