Moving a bit within a byte using bitfield or bitwise operators

Question

Is there an elegant way of moving a bit within a byte (or word/long). For simplicity, lets use a simple 8-bit byte and just one bit to move within the byte.

Given a bit number, based on 0-7 Least-sig-bit to most-sig-bit, (or bits 1-8 if you'd rather), I would like to move a bit from one position to another:

7654 3210 <bit position
0101 1010 <some binary value
--x- --y- <move bit from x to y
0111 0100 <new value with x moved to y and intervening bits shifted left

So, x at bit position 5 moves to y at bit position 1, bits 0,6,7 stay unchanged. Bits 2,3,4 are shifted left to 'make room' for the bit moved from 5 to 2. This is just an example.

It is important that the bit moves, not swapped with its target. There are numerous exampls of bits that swap, but that is quite trivial.

The solution ideally would use simple bit-twiddling and bitwise operators. Assume language agnostic, bit simple AND/OR/XOR, NOT, SHIFT Left/Right / ROTATE or similar instructions would be fine in any combination, plus any other basic arithmetic operator, eg: mod, addition/subtraction etc. Even working psuedo-code would be ok. Alternatively, a bit array or bitfield type structure would probably be straightforward.

In addition to the actual bit move, I would like to find a way to :

• Move any bit up or down.
• Specify the bit number source/destination in any convenient format: eg: 6>2 implies shift down, 3>7 shift up or start-bit +/- offset: 6-4 or 3+4, or bit weighted: bit 6=64 to bit 3=8.
• Possibly extendable from byte to unsigned int, long, etc.
• (Ideally, be extendable to more than one bit at a time, probably adjacent bits if easier)

Performance is not a major issue, but something elegant is likley to be plenty fast enough.

My own niaive approach would be to identify the source and target bit positions, decide if shift up or down, take a shifted copy, mask off the static bits and find the source bit, merge the static and shifted bits and somehow set/clear the target bit. However, while the theory seems good, an elegant implementation is beyond me.

I realise that a precompiled lookup table could be built for a byte, but if this is to be extended to integers/longs, this would be impractical for me.

Any help appreciated. Thanks in advance.

Answer 1

First, an observation about the original problem, and the subsequent extensions that you mention:

The "moving a bit" operation that you describe is really a rotation of a contiguous range of bits. In your example, you are rotating bits 1-5 inclusive, by one bit to the left:

  7   6   5   4   3   2   1   0          7   6   5   4   3   2   1   0
+---+---+---+---+---+---+---+---+      +---+---+---+---+---+---+---+---+
| 0 | 1 | 0<--1<--1<--0<--1 | 0 |  ->  | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
+---+---+-|-+---+---+---+-^-+---+      +---+---+---+---+---+---+---+---+
          |               |
          +---------------+

If you consider a more general form of this operation to be "rotate a range of bits left by some amount" with three parameters:

1. the least significant bit to include in the rotation
2. the most significant bit to include in the rotation
3. the number of bits to rotate by

then it becomes a single basic primitive which can perform all of the things you want to do:

• you can obviously move any bit (choose appropriate least/most significant bit paramaters);
• you can rotate left or right, because if you are rotating a range of n bits, then a rotation right by k bits is the same thing as a rotation left by n - k bits;
• it trivially generalises to any bit width;
• by definition we can rotate more by more than one bit at a time.

So now, all that's needed is to construct this primitive...

---

To start with, we're almost certainly going to need a bit mask for the bits we care about.

We can form a mask for bits 0 - n by shifting a 1 by n + 1 bits to the left, then subtracting 1. e.g. a mask for bits 0-5 would be (in binary):

00111111

...which can be formed by taking a 1:

00000001

...shifting 5+1 = 6 bits to the left:

01000000

...and subtracting 1 to give:

00111111

In C, this would be (1 << (bit + 1)) - 1. But there is a subtlety here, for C at least (and I apologise for the digression when you've tagged this as language-agnostic, but this is important, and there are probably similar issues in other languages too): a shift by the width of your type (or more) leads to undefined behaviour. So if we were trying to construct a mask for bits 0-7 for an 8-bit type, the calculation would be (1 << 8) - 1, which would be undefined. (It might work on some systems and some compilers, but wouldn't be portable.) There are also undefined behaviour issues with signed types in the case where you would end up shifting into the sign bit.

Fortunately, in C, we can avoid these problems by using an unsigned type, and writing the expression as (1 << bit) + (1 << bit) - 1. Arithmetic with unsigned n-bit values is defined by the standard to be reduced modulo 2ⁿ, and all of the individual operations are well-defined, so we're guaranteed to get the right answer.

(End of digression.)

OK, so now we have a mask for bits 0 - msb. We want to make a mask for bits lsb - msb, which we can do by subtracting the mask for bits 0 - (lsb-1), which is (1 << lsb) - 1. e.g.

  00111111      mask for bits 0-5:  (1 << 5) + (1 << 5) - 1
- 00000001      mask for bits 0-0:  (1 << 1) - 1
  --------                         -------------------------------
  00111110      mask for bits 1-5:  (1 << 5) + (1 << 5) - (1 << 1)

So the final expression for the mask is:

mask = (1 << msb) + (1 << msb) - (1 << lsb);

The bits to be rotated can be selected by a bitwise AND with the mask:

to_rotate = value & mask;

...and the bits that will be left untouched can be selected by a AND with the inverted mask:

untouched = value & ~mask;

The rotation itself can be performed easily in two parts: first, we can obtain the leftmost bits of the rotated portion by simply rotating to_rotate left and discarding any bits that fall outside the mask:

left = (to_rotate << shift) & mask;

To get the rightmost bits, rotate to_rotate right by (n - shift) bits, where n is the number of bits we're rotating (this n can be calculated as msb + 1 - lsb):

right = (to_rotate >> (msb + 1 - lsb - shift)) & mask;

The final result can be obtained by combining all the bits from untouched, left, and right:

result = untouched | left | right;

Your original example would work like this (msb is 5, lsb is 1, and shift is 1):

    value = 01011010

    mask  = 00111110   from (1 << 5) + (1 << 5) - (1 << 1)

            01011010   value
          & 00111110   mask
          ----------
to_rotate = 00011010

            01011010   value
          & 11000001   ~mask  (i.e. inverted mask)
          ----------
untouched = 01000000

            00110100   to_rotate << 1
          & 00111110   mask
          ----------
     left = 00110100

            00000001   to_rotate >> 4  (5 + 1 - 1 - 1 = 4)
          & 00111110   mask
          ----------
    right = 00000000

            01000000   untouched
            00110100   left
          | 00000000   right
          ----------
   result = 01110100

Here's a different example with a 16-bit input value, msb = 15, lsb = 4, and shift = 4 (which rotates the top 3 hex digits of a 4-digit hex value):

    value = 0101011001111000   (0x5678)

    mask  = 1111111111110000   from (1 << 15) + (1 << 15) - (1 << 4)

            0101011001111000   value
          & 1111111111110000   mask
          ------------------
to_rotate = 0101011001110000

            0101011001111000   value
          & 0000000000001111   ~mask
          ------------------
untouched = 0000000000001000

            0110011100000000   to_rotate << 4
          & 1111111111110000   mask
          ------------------
     left = 0110011100000000

            0000000001010110   to_rotate >> 8  (15 + 1 - 4 - 4 = 8)
          & 1111111111110000   mask
          ------------------
    right = 0000000001010000

            0000000000001000   untouched
            0110011100000000   left
          | 0000000001010000   right
          ------------------
   result = 0110011101011000   =  0x6758

Answer 2

Here's a working implementation in C that is not highly optimised but which might at least serve as a starting point for any further implementations. It works with ints but you can adapt it for any word size, or just use it as is and mask out any unwanted high order bits (e.g. if you are working with individual bytes). I broke the functionality down into two lower level routines for extracting a bit and inserting a bit - these may have other uses, I imagine.

//
// bits.c
//

#include <stdio.h>
#include <stdlib.h>

//
// extract_bit
//
// extract bit at given index and move less significant bits left
//

int extract_bit(int *word, int index)
{
    int result = (*word & (1 << index)) != 0;
    int mask = (1 << index) + (1 << index) - 1;
    *word = ((*word << 1) & mask) | (*word & ~mask);
    return result;
}

//
// insert_bit
//
// insert bit at given index and move less significant bits right
//

void insert_bit(int *word, int index, int val)
{
    int mask1 = (1 << index) + (1 << index) - 1;
    int mask2 = (1 << index) - 1;
    *word = ((*word >> 1) & mask2) | (*word & ~mask1) | (val << index);
}

//
// move_bit
//
// move bit from given src index to given dest index
//

int move_bit(int *word, int src_index, int dest_index)
{
    int val = extract_bit(word, src_index);
    insert_bit(word, dest_index, val);
    return val;
}

int main(int argc, char * argv[])
{
    if (argc > 2)
    {
        int test = 0x55555555;
        int index1 = atoi(argv[1]);
        int index2 = atoi(argv[2]);

        printf("test (before) = %#x\n", test);
        printf("index (src) = %d\n", index1);
        printf("index (dest) = %d\n", index2);

        move_bit(&test, index1, index2);

        printf("test (after) = %#x\n", test);
    }

    return 0;
}

Answer 3

This likely doesn't qualify as "elegant," but you might be able to cram it into one line if that is your kind of thing? The plan is to split the number into four pieces (shouldn't be hard with bit operations, right?), do the appropriate things to them, and then put the three pieces back together.

              Number: 01x1 10y1
       P1 (before x): 0100 0000
     P2 (just bit x): 00x0 0000
P3 (between x and y): 0001 10y0
        P4 (after y): 0000 0001

Then the number you want is [P1] + [P3 shifted up by 1] + [P2 shifted down by 4] + [P4].

                  P1: 0100 0000
P2 shifted down by 3: 0000 00x0
  P3 shifted up by 1: 0011 0y00
                  P4: 0000 0001

                 Sum: 0111 0yx1               

Answer 4

Are you using bits to conserve space? Is it REALLY needed?

You might be better off with a list class that allows you to remove and insert items in the list. In your case the items would be Booleans.