Rotating an array of bits in C

Question

I've just started learning C and I'm having some problems with some code I want to write.

Basically I have this struct that is a bit array, with the number of bits in the array, and a pointer to a buffer of chars, that stores the bits.

My strategy for rotating the bit array is simply taking the number of rotations (mod the length to avoid full rotations) and using a simple reversal algorithm to rotate the array.

EDIT:

However, my problem is that I want to rotate the bits in the actual buffer.

I also want to be able to rotate a subsequence of bits within the entire bit array. So for 1101101, I might want to rotate (0-indexed from the left) the subsequence starting at index 2 and ending at index 5. I'm not entirely sure how to use my char buffer to do this.

Thanks for the help!

struct arrayBits{
   size_t numBits;
   char *buf;
 }

The buf array holds 8-bit integers, not bools as I previously mentioned.

The way that I can access and set an individual bit is just by indexing into the byte that holds the bit I want (so for an array ab, ab->buf[index_of_desired_bit/8] and then performing some bitwise operations on it to change the value, for performance reasons.

EDIT: Thanks to everyone for all the suggestions. I've looked at all of them and I believe I understand the code better. Here's the code I ended up writing, however, I think there are some problems with it.

While it passes some of my basic test cases, it seems to run a little too fast on an bitarray of size 98775 bits, randomly filled. By this I mean, is there some case in which my code just outright fails and crashes? The test cases do three rotations, in a row, on the full 98775-bit array. One rotation of -98775/4 (<--this is a size_t, so wrap around?), one rotation of 98775/4, and then a final rotation of 98775/2.

Is there something I'm missing or some problem I'm not seeing?

/*Reverse a bit array*/
/*v1.1: basic bit reversal w/o temp variable*/
static void arrayReversal(bitarray_t *ba, size_t begin, size_t end){
while(begin < end)
{
    bitarray_set(ba, begin, (bitarray_get(ba, begin) ^ bitarray_get(ba, end))); /*x = x ^ y*/
    bitarray_set(ba,  end,   (bitarray_get(ba, begin) ^ bitarray_get(ba, end))); /*y = x ^ y*/
    bitarray_set(ba, begin, (bitarray_get(ba, begin) ^ bitarray_get(ba, end))); /*x = x ^ y*/
    begin++;
    end--;
}

}


/*Main Rotation Routine*/
void bitarray_rotate(bitarray_t *ba, size_t bit_off, size_t bit_len, ssize_t bit_right_amount) {
assert(bit_off + bit_len <= ba->bit_sz);
assert(bit_off + bit_len > 0);

if(bit_off + bit_len > ba->bit_sz || bit_off + bit_len < 0) 
    {
        printf("\nError: Indices out of bounds\n");
        return;
    }

/*Find index to split bitarray on*/
if(bit_len == 0) return; //Rotate only 1 bit i.e. no rotation

size_t reversal_index;
reversal_index  = modulo(-bit_right_amount, bit_len);

if(reversal_index == 0) return; //No rotation to do

/*3 bit string reversals*/

assert(reversal_index - 1 + bit_off < ba->bit_sz);
/* Reverse A*/
arrayReversal(ba, bit_off, reversal_index - 1 + bit_off); 
assert(reversal_index + bit_off < ba->bit_sz);

/*Reverse B*/
arrayReversal(ba, reversal_index + bit_off, (bit_off + bit_len - 1));

/*Reverse ArBr*/    
arrayReversal(ba, bit_off, (bit_off + bit_len -1));

}

Answer 1

I suggest you use bit-level operations (>>,<<,~,&,|) rather than wasting space using int. Even so, using an int array, to rotate, pass the left & right index of substring:

void rotate ( struct arrayBits a, int left , int right )
{

   int i;
   int first_bit;

   if(*( a.buf + right ) == 1) first_bit = 1; 
   else first_bit = 0;

   for( i = left+1 ; i <= right ; i++ )
   {
      *( a.buf + i )=*( a.buf + i - 1 ); 
   }

   *a.buf = first_bit;    

}

Example:

If struct_array is 010101,

rotate (struct_array,0,5); => rotates whole string 1 int to right

o/p: 101010

rotate (struct_array,2,4); => rotates substring 1 int to right

o/p: 01 001 1

To reverse the bit array call the rotate() function on the substring, size_of_substring times.

Answer 2

You dont need an extra buffer for rotate (only for output). You should implement a function for one rotate and loop this, eg: (right-shift variation)

char *itoa2(char *s,size_t i)
{
  *s=0;
  do {
    memmove(s+1,s,strlen(s)+1);
    *s='0'+(i&1);
  } while( i>>=1 );
  return s;
}

size_t bitrotateOne(size_t i)
{
  return i>>1 | (i&1) << (sizeof i<<3)-1;
}

...

size_t i=12,num=17;
char b[129];
while( num-- )
{
  i = bitrotateOne(i);
  puts( itoa2(b,i) );
}

Answer 3

I would suggest a pointer/offset to a starting point of a bit in the buffer instead of rotating. Feel free to overload any operator that might be useful, operator[] comes to mind. A rotate(n) would simply be a offset+=n operation. But I find the purpose of your comment about -"However, my problem is that I want to rotate the actual buffer" confusing.

Answer 4

Well the easy way to start is to consider how to rotate the bits in a single value. Let's say that you have x, which is an N-bit value and you want to rotate it by k places. (I'm only going to look at rotating upwards/left, it is easy to convert to downwards/right). The first thing to observe is that if k=N then x is unchanged. So before rotating we want to reduce k modulo N to throw away complete rotations.

Next we should observe that during the rotation the k upper-bits will move to the bottom of the value, and the lower N-k bits will move up k places. This is the same as saying that the top k-bits move down N-k places. The reason that we phrase it this way is that C has shift operators, but not rotation.

In psuedo-C we can say:

#define N sizeof(type)*8
type rotate(type x, int k) {
  type lower = x & ((1 << (N-k)) - 1);
  type upper = x >> (N-k) & ((1 <<k)-1);
  return upper | lower;
}

This takes care of the simple atomic case, simply replace type with char or int as appropriate. If type is unsigned then the mask on the value of upper is unnecessary.

The next thing to consider is rotating in an array of values. If you think of the above code as glueing together two halves of a value then for the more complicated case we need to glue together upper and lower parts from different places in the array. If k is small then these places are adjacent in the array, but when k>N we are rotating through more than one intermediate word.

In particular if we are rotating up k places then we are moving bits from k/N words away in the array, and the N bits can span floor(k/N) and ceil(k/N) locations away in the array. Ok, so now we're ready to put it all together. For each word in the array the new upper N-(k mod N) bits will be the lower bits of floor(k/N) words away, and the new lower (k mod N) bits will be the upper bits of ceil(k/N) words away.

In the same psuedo-C (i.e replace type with what you are using) we can say:

#define N sizeof(type)*8
#define ARR_SIZE ...
type rotate(type *x, int k,type *out) {
  int r = k % N;
  int upperOff = k/N;
  int lowerOff = (k+N-1)/N;
  for(int i=0; i<ARR_SIZE; i++) {
    int lowerPos = (i + ARR_SIZE - lowerOff) % ARR_SIZE
    int upperPos = (i + ARR_SIZE - upperOff) % ARR_SIZE
    type lower = x[lowerPos] & ((1 << (N-k)) - 1)
    type upper = x[upperPos] >> (N-k) & ((1 <<k)-1)
    out[i] = upper | lower;
  }
}

Anyway, that's a lot more than I was intending to write so I'll quit now. It should be easy enough to convert this to a form that works inplace on a single array, but you'll probably want to fix the types and the range of k first in order to bound the temporary storage.

If you have any more problems in this area then one place to look is bitmap sprite graphics. For example this rotation problem was used to implement scrolling many, many moons ago in 8-bit games.

Answer 5

Since your criteria is so complex, I think the easiest way to do it would be to step through each bit and set where it would be in your new array. You could speed it up for some operations by copying a whole character if it is outside the shifted bits, but I can't think of how to reliably do shifting taking into account all the variables because the start and end of the shifted sequence can be in the middle of bytes and so can the end of the entire bits. The key is to get the new bit position for a bit in the old array:

j = (i < startBit || i >= startBit + length) ? i : 
    ((i - startBit + shiftRightCount) % length) + startBit;

Code:

#include "stdafx.h"
#include <stdlib.h>
#include <string.h>

typedef struct {
   size_t numBits;
   unsigned char *buf;
} ARRAYBITS;

// format is big endian, shiftint left 8 bits will shift all bytes to a lower index
ARRAYBITS rotateBits(ARRAYBITS *pOriginalBits, int startBit, int length, int shiftRightCount);
void setBit(unsigned char *buf, int bit, bool isSet);
bool checkBit(unsigned char *buf, int bit);
ARRAYBITS fromString(char *onesAndZeros);
char *toString(ARRAYBITS *pBits);

int _tmain(int argc, _TCHAR* argv[])
{
    char input[1024];
    ARRAYBITS bits = fromString("11110000110010101110"); // 20 bits
    ARRAYBITS bitsA = rotateBits(&bits, 0, bits.numBits, 1);
    ARRAYBITS bitsB = rotateBits(&bits, 0, bits.numBits, -1);
    ARRAYBITS bitsC = rotateBits(&bits, 6, 8, 4);
    ARRAYBITS bitsD = rotateBits(&bits, 6, 8, -2);
    ARRAYBITS bitsE = rotateBits(&bits, 6, 8, 31);
    ARRAYBITS bitsF = rotateBits(&bits, 6, 8, -31);
    printf("Starting   : %s\n", toString(&bits));
    printf("All right 1: %s\n", toString(&bitsA));
    printf("All left 1 : %s\n", toString(&bitsB));
    printf("\n");
    printf("           :       ********\n");
    printf("Starting   : %s\n", toString(&bits));
    printf("6,8,4      : %s\n", toString(&bitsC));
    printf("6,8,-2     : %s\n", toString(&bitsD));
    printf("6,8,31     : %s\n", toString(&bitsE));
    printf("6,8,-31    : %s\n", toString(&bitsF));
    gets(input);
}

ARRAYBITS rotateBits(ARRAYBITS *pOriginalBits, int startBit, int length, int shiftRightCount)
{
    // 0-8 == 1, 9-16 == 2, 17-24 == 3
    ARRAYBITS newBits;
    int i = 0, j = 0;
    int bytes = 0;
    while (shiftRightCount < 0)
        shiftRightCount += length;
    shiftRightCount = shiftRightCount % length;

    newBits.numBits = pOriginalBits->numBits;
    if (pOriginalBits->numBits <= 0)
        return newBits;

    bytes = ((pOriginalBits->numBits -1) / 8) + 1;
    newBits.buf = (unsigned char *)malloc(bytes);
    memset(newBits.buf, 0, bytes);
    for (i = 0; i < pOriginalBits->numBits; i++) {
        j = (i < startBit || i >= startBit + length) ? i : ((i - startBit + shiftRightCount) % length) + startBit;
        if (checkBit(pOriginalBits->buf, i))
        {
            setBit(newBits.buf, j, true);
        }
    }
    return newBits;
}

void setBit(unsigned char *buf, int bit, bool isSet)
{
    int charIndex = bit / 8;
    unsigned char c = 1 << (bit & 0x07);
    if (isSet)
        buf[charIndex] |= c;
    else
        buf[charIndex] &= (c ^ 255);
}

bool checkBit(unsigned char *buf, int bit)
{
    // address of char is (bit / 8), bit within char is (bit & 7)
    int index = bit / 8;
    int b = bit & 7;
    int value = 1 << b;
    return ((buf[index] & value) > 0);
}

ARRAYBITS fromString(char *onesAndZeros)
{
    int i;
    ARRAYBITS bits;
    int charCount;

    bits.numBits = strlen(onesAndZeros);
    charCount = ((bits.numBits -1) / 8) + 1;
    bits.buf = (unsigned char *)malloc(charCount);
    memset(bits.buf, 0, charCount);
    for (i = 0; i < bits.numBits; i++)
    {
        if (onesAndZeros[i] != '0')
            setBit(bits.buf, i, true);
    }
    return bits;
}

char *toString(ARRAYBITS *pBits)
{
    char *buf = (char *)malloc(pBits->numBits + 1);
    int i;
    for (i = 0; i < pBits->numBits; i++)
    {
        buf[i] = checkBit(pBits->buf, i) ? '1' : '0';
    }
    buf[i] = 0;
    return buf;
}