Как запрограммировать «колесо» битов

Question

Я хотел бы запрограммировать «колесо» с определенной длиной битов и с одним битом на «true». Когда я вращаю колесо (90 °), этот бит тоже должен вращаться.

Как длина: = 4:

1    0    0    0    1 
    0 0 ==> 0 1 ==> 0 0 ==> 1 0 ==> 0 0 
    0    0    1    0    0 

ИЛИ

0001 ==> 0010 ==> 0100 ==> 1000 ==> 0001 

После того, как колесо вращается полная Иная функция должна быть вызвано.

Что было бы хорошим способом кодировать это?

Answer 1

Поскольку вы знаете, что есть только один 1 бит, нет никакого смысла в хранении все в 0 «s. Просто сохраните позицию 1.

struct Wheel { 
    Wheel(int size) 
    : _size(size) 
    , _onePos(0) {} 

    void rotate() { 
     ++_onePos; 
     if(_onePos == _size) { 
      _onePos = 0; 
      onFullRotation(); 
     } 
    } 

    unsigned int bits() const { 
     return 1u << _onePos; 
    } 

private: 
    void onFullRotation() { 
     std::cout << "<full rotation>"; 
    } 

    int const _size; 
    int _onePos; 
}; 

Live on Coliru

Answer 2

Эта операция известна как поворот бит.

unsigned rotate_left(unsigned x, unsigned num_bits, int delta) { 
    unsigned rdelta = delta % num_bits; 
    unsigned mask = (1 << num_bits) - 1; 
    return ((x << rdelta) | (x >> (num_bits - rdelta))) & mask; 
} 

Это будет вращать bitwheel x, содержащий num_bits бит, оставленных delta бит. Отрицательные сдвиги также должны работать. Эквивалентную функцию rotate_right можно получить, изменив << на >> и наоборот.

Если num_bits - 32, и вам необходимо выполнить эту операцию очень быстро, вы можете использовать встроенные инструкции для поворота машины.

Добавления: чтобы проверить крайний правый (нулевой) бит, использование курса:

if (x & 1) { ... 

Чтобы проверить битную N:

if (x & (1 << N)) { ... 

Если вам нужно больше, чем 32 бита, использовать unsigned long или unsigned long long (зависит от вашей платформы). Если вам нужно произвольное количество бит, это решение не будет работать - вам нужно будет использовать что-то на основе, например. на std::bitset, как во втором ответе, или на vector<bool>.

Answer 3

Ваше «колесо» может быть представлено как поле бит в вашей памяти. Если требуемая длина меньше 64, вы можете использовать любой целочисленный тип для ее реализации. это просто:

void shift_clockwise(unsigned long long *wheel, int size) { 
    unsigned long long first_bit = (*wheel) & 1ll; 
    (*wheel) = ((*wheel) >> 1) & (first_bit << (size-1));   
} 

Если размер больше, то вы можете использовать std::bitset, например:

void shift_clockwise(std::bitset<wheel_size>& wheel) { 
    bool first_bit = wheel.test(0); 
    wheel >>= 1; 
    set(wheel.size()-1, first_bit); 
}