Я только начал изучать C и у меня возникли проблемы с кодом, который я хочу написать.
По сути, у меня есть эта структура, представляющая собой битовый массив с количеством битов в массиве и указатель на буфер символов, в котором хранятся биты.
Моя стратегия для вращения массива битов - просто взять число вращений (изменить длину, чтобы избежать полных вращений) и использовать простой алгоритм обращения для вращения массива.
EDIT:
Однако моя проблема в том, что я хочу повернуть биты в реальном буфере.
Я также хочу иметь возможность вращать подпоследовательность битов во всем битовом массиве. Поэтому для 1101101 я мог бы захотеть повернуть (0-индексированная слева) подпоследовательность, начиная с индекса 2 и заканчивая индексом 5. Я не совсем уверен, как использовать мой буфер символов для этого.
Спасибо за помощь!
struct arrayBits{
size_t numBits;
char *buf;
}
Массив buf содержит 8-битные целые числа, а не bools, как я упоминал ранее.
Я могу получить доступ к отдельному биту и установить его, просто индексировав в байт, содержащий нужный бит (так для массива ab, ab-> buf [index_of_desired_bit / 8], а затем выполнив некоторые побитовые операции над чтобы изменить значение, из соображений производительности.
РЕДАКТИРОВАТЬ: Спасибо всем за все предложения. Я посмотрел на все из них, и я думаю, что я понимаю код лучше. Вот код, который я закончил писать, однако, я думаю, что есть некоторые проблемы с ним.
Несмотря на то, что он проходит некоторые из моих базовых тестовых случаев, он, кажется, работает слишком быстро на битовой матрице размером 98775 бит, заполненной случайным образом. Под этим я подразумеваю, есть ли какой-то случай, когда мой код просто терпит неудачу и вылетает? Тестовые случаи выполняют три чередования подряд на полном 98775-битном массиве. Один оборот -98775/4 (<- это size_t, так что оборачиваться?), Один поворот 98775/4, а затем окончательный поворот 98775/2. </p>
Что-то я пропускаю или какую-то проблему я не вижу?
/*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));
}