How to reverse bits in only the most significant half of an integer and leave the other half (least significant bits) untouched?

Question

I am trying to practice bit manipulation with this problem. I attempted to solve this question by using an 8 bit integer. For example, if you have an input of 1101 1110, the output will be 1011 1110. I will show the steps I took to arrive to this output.

Input: 1101 1110
Save less significant half of integer: (1101 1110) & 0x0f = 0000 1110
Reverse the more significant half of integer: (1101 1110) >> 4 = 0000 1101
    int mostSigHalf = 0b00001101;
    int result = 0;

    for(int i=0; i<8; i++)
    {
        result = (result<<1) | (mostSigHalf&1);
        mostSigHalf = mostSigHalf>>1;
    }

The reversed part is now 1011 0000

Lastly, XOR the reversed most significant half of the integer with the least significant half that got saved:
(1011 0000) ^ (0000 1110) = 1011 1110

How can I extend this method of only reversing the bits of the most significant half of an integer of any size (not just limited to 8 bits)? If anyone has any suggestions or other methods to solve this problem than what I came up with, please do share!

Answer 1

You need a series of masks and shifts. There is more than one way to come up with a sequence that does what you need. One way to approach it would be:

#include <stdio.h>

int main (void) {

    unsigned char   u = 0xde,
                    v = u >> 4,                           /* high nibble as v */
                    w = v & 0x3,                          /* bottom 2 bits */
                    x = (v & 0xc) >> 2,                   /* top 2 bits */
                    y = ((w >> 1) | ((w & 1) << 1)) << 2, /* rev bot/shift */
                    z = (x >> 1) | ((x & 1) << 1);        /* rev top */

    /* form high-nibble shift by 4, or with original bottom nibble */
    printf ("orig: 0x%02hhx\nrevd: 0x%02hhx\n", u, ((y | z) << 4) | (u & 0xf));

}

Example Use/Output

$ ./bin/bitrevhighnibble
orig: 0xde
revd: 0xbe

Put Together In a Function

Since you are looking to extend your current function, you can simply write another short function that takes a byte and performs the same series of shifts and masks and returns the results you need:

unsigned char swaphighnibblepairs (unsigned char u) {

    unsigned char   v = u >> 4,                         /* high nibble as v */
                    w = v & 0x3,                        /* bottom 2 bits */
                    x = (v & 0xc) >> 2,                 /* top 2 bits */
                    y = ((w >> 1) | ((w & 1) << 1)),    /* rev bottom */
                    z = (x >> 1) | ((x & 1) << 1);      /* rev top */

    /* form high-nibble shift by 4, OR with original bottom nibble */
    return (((y << 2) | z) << 4) | (u & 0xf);
}

Explanation

Looking further that the sequence beginning with u = 0xde; (your bit sequence 1101 1110), you start by isolating the top 4-bits (the high-nibble),

    unsigned char   v = u >> 4,                         /* high nibble as v */

With the high-nibble in v, you can then mask and isolate the bottom 2-bits and mask and shift top 2-bits, e.g.

                    w = v & 0x3,                        /* bottom 2 bits */
                    x = (v & 0xc) >> 2,                 /* top 2 bits */

What is left is revering each bit in w and x:

                    y = ((w >> 1) | ((w & 1) << 1)),    /* rev bottom */
                    z = (x >> 1) | ((x & 1) << 1);      /* rev top */

The final result is arrived at by OR'ing (y << 2) | z and shifting that nibble by 4 to the left to become the new high-nibble and OR'ing that with the original low-nibble isolated by a simple mask of the original high-nibble: (((y << 2) | z) << 4) | (u & 0xf)

You can re-arrange the order of the masks and shifts and probably come up with a shorter route, or combine more of the operations together, but for the cost of a few extra bytes, spreading them out may make it easier to think through.

Let me know if you have further questions.