Как я могу получить "потерянный" бит от сдвига битов?

Question

Я хочу сдвинуть бит в переменной и сохранить сдвинутый бит в логическом значении.

Что-то вроде:

unsigned int i = 1;
bool b = rshift(&i); // i now equals 0 and b is set to true

Как это можно сделать?

Answer 1

Вы должны захватить бит до сдвига:

bool rshift(unsigned int* p) {
    bool ret = (*p) & 1;
    *p >>= 1;
    return ret;
}

Answer 2

Ты не.Вы должны проверить это до сдвига:

bool
rshift( unsigned& i )
{
    bool results = (i & 0x01) != 0;
    i >>= 1;
    return results;
}

(Это просто для сдвига вправо. Для сдвига влево вы должны знать количество бит в слове.)

Answer 3

Чтобы сделать это для любой смены и любого типа, отмените операцию (чтобы проверить, что вы что-то потеряли).

template <typename T> bool rshift(T& val) {
  T const original = val;
  return ((val >>= 1) << 1) != original;
}
template <typename T> bool lshift(T& val) {
  T const original = val;
  return ((val <<= 1) >> 1) != original;
}

Answer 4

Если вы ищете функцию поворота, вы можете попробовать следующее.

Во-первых, у вас есть мета-функция для получения количества битов значения, которое должно быть повернуто (примечание: 8*sizeof(T) не будет переносимым; стандарт требует только 8 бит):

#include <climits>
template <typename T>
struct bits { enum { value = CHAR_BIT * sizeof(T) }; };

Далее определите функцию для вращения вправо. Он делает это, применяя сдвиг вправо, как и ожидалось, и сдвиг влево, чтобы сдвинуть вверх то, что было бы отменено в противном случае:

template <unsigned int N, typename T>
T rotate_right (T value)
{
    enum { left = bits<T>::value - N };
    return (value>>N) | (value<<left);
}

Имеют функцию диагностики для тестирования и проверки:

#include <iostream>

template <typename T>
void print_bits (std::ostream &os, T value)
{
    for (unsigned int i=bits<T>::value; i!=0; --i)
        os << ((value>>(i-1))&1);
}

    int main () {
    char c = 1,
         c_ = rotate_right<1>(c);

    unsigned long long ull = 0xF0F0C0C050503030, 
                       ull_ = rotate_right<63>(ull);

    std::cout << "c ="; print_bits(std::cout, c);  std::cout << '\n';
    std::cout << "c'="; print_bits(std::cout, c_); std::cout << '\n';
    std::cout << "ull ="; print_bits(std::cout, ull);  std::cout << '\n';
    std::cout << "ull'="; print_bits(std::cout, ull_); std::cout << '\n';
}

Выход:

c =00000001
c'=10000000
ull =1111000011110000110000001100000001010000010100000011000000110000
ull'=1110000111100001100000011000000010100000101000000110000001100001

Поворот влево может быть реализован аналогично или с точки зрения поворота вправо.

Что касается производительности, g ++ обнаруживает идиому и использует инструкцию поворота на x86 и amd64.

g++ -std=c++0x -S main.cc
cat main.s

...
sarl %eax
...

Answer 5

Вот альтернатива выдвинутым на данный момент предложениям:

bool rshift(int32_t &i) {
  long long i2 = (static_cast<int64_t>(i) << 31);
  i = (i2 >> 32);
  return static_cast<int32_t>(i2);
}

Предполагается, что int - это то, что int обычно означает в наши дни, то есть int32_t.Он копирует его в int64_t, затем выполняет сдвиг, копирует старшие 32 бита в i и затем возвращает младшие 32 бита (которые содержат сдвинутый 1) в виде логического значения.

Iне знаю, быстрее ли это, чем другие подходы. дополнительное преимущество этого общего подхода заключается в том, что его можно использовать для получения более одного бита, например, если вы сдвигаете на 2 или более бит.