1

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));

}

Improve this question
7
  • 1
    Can you show an example? With the buffer before and after, and the definition of your struct Commented Sep 18, 2010 at 16:31
  • Can you show us some code, like the layout of the struct. Commented Sep 18, 2010 at 16:31
  • 1
    Why don't you show us your attempt, so that we can correct it if necessary? Commented Sep 18, 2010 at 16:52
  • Are you using the char * to store bits which are of type bool? Aren't bools of type int? Commented Sep 18, 2010 at 16:53
  • The way that I did it is by accessing each bit individually. So basically, I just reversed the bit array (or subsequence of the bitarray) by swapping them out in a loop. The way the reversal algorithm I'm using works is for a sequence of bits R, based on the number of rotations d, I can separate R into two arrays A=R[0..d-1] and B=R[d...n-1]. Then I reverse A to get AreversedB, reverse B to get AreversedBreversed and then reverse it all to get BA. This leads to the correct number of rotations (all to the left) and the right answer. Commented Sep 18, 2010 at 17:02

5 Answers 5

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

The major (and extremely important) detail about the original question is that the rotation has to be performed in-place, i.e. with O(1) additional memory. Your algorithm required an independent output array. Doing it in-place is an algorithm from a completely different realm, which cannot be built directly from what you did above. For in-place solution there are three well-known approaches: juggling, reversal and block-swapping (see "Programming Pearls").
These approaches are usually used for ordinary array rotation, but bit-array rotation is not really different. The OP attempted to implement the reversal approach. I would say that performance-wise the block-swapping approach looks much more promising in this case (for the very same reason it works best with arrays). Also, block-swapping is much easier to make work on per-word basis, as opposed to the inefficient per-bit implementation used in the OP's code.
The major and important detail in the original question was added after I replied :) The use of the separate output array was actually for clarity given the original question. Calling the algorithm a completely different realm is a bit of a reach though. As k is constant during the loop it is trivial to rewrite the output emission into word-swapping code using a constant number of variables. For performance and simplicity it would probably be best to pick a number of swap variables that matches the size of a cache line.
Well, I disagree. Algorithms like "in-place merging" and "in-place rotation" are classic examples of algorithms that demonstrate limited applicability (or even total uselessness) of non-in-place techniques to some in-place problems. Remember that the rotation distance k is not limited to the size of a single word. Again, the problem is virtually identical to array rotation. There's no "naive" general solution with constant memory, i.e. it cannot be solved by sequential rotation of the words in the array.
The approach you used above will require non-constant memory, i.e. the amount will depend on k. What you are trying to say about k being constant is not clear to me. k is not constant, it is an input parameter. Any solution that requires O(k) additional memory is not a constant-memory solution. The OP's solution (reversal approach), on the other hand, requires only O(1) extra memory. A block-swapping approach will also require O(1) memory, while being more efficient than reversal.
|
0

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.

Improve this answer

Comments

0

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) );
}
Improve this answer

1 Comment

The question is tagged performance-tuning. This is not exactly the quickest way...
0

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;
}
Improve this answer

1 Comment

If it weren't for the memory leaks, I'd give you +1
0

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.

Improve this answer

4 Comments

Note that a value of bool data type will not be one-bit wide; it will be at least the minimum addressable width on the machine (8 bits, or a byte, on most machines). So, you will take up at least 8 times as much room as you would need using bitwise operations if you take this approach.
@Brian Campbell, I think that is a question we can all ask of CCSab.
I made another mistake, once again sorry, beginner at C. My char buf array holds 8-bit integers, so an individual byte. I've updated the OP to reflect how I access the individual bits. For performance reasons, I'm trying to avoid costly operations. I feel that accessing individual bits, instead of dealing with the entire 1-byte char instead might affect performance significantly.
You cannot access individual bits instead of whole chars, the processor cannot address smaller values than a char. Actually, to access the value of a single bit you have to fetch the whole char and and/shift it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.