C++
Бит-манипуляция

замечания

#include <bitset>

Установка бит

C-стиль бит манипуляции

Бит может быть установлен с помощью побитового оператора OR ( | ).

// Bit x will be set
number |= 1LL << x; 

Использование std :: bitset

set(x) или set(x,true) - устанавливает бит в положение x в 1 .

std::bitset<5> num(std::string("01100"));
num.set(0);      // num is now 01101
num.set(2);      // num is still 01101
num.set(4,true); // num is now 11110

Очистка бит

C-стиль бит-манипуляции

Бит можно очистить с помощью побитового оператора И ( & ).

// Bit x will be cleared
number &= ~(1LL << x);

Использование std :: bitset

reset(x) или set(x,false) - очищает бит в позиции x .

std::bitset<5> num(std::string("01100"));
num.reset(2);     // num is now 01000
num.reset(0);     // num is still 01000
num.set(3,false); // num is now 00000

Переключение немного

C-стиль бит-манипуляции

Бит можно переключить с помощью оператора XOR ( ^ ).

// Bit x will be the opposite value of what it is currently
number ^= 1LL << x;

Использование std :: bitset

std::bitset<4> num(std::string("0100"));
num.flip(2); // num is now 0000
num.flip(0); // num is now 0001
num.flip();  // num is now 1110 (flips all bits)

Проверка бит

C-стиль бит-манипуляции

Значение бит может быть получено путем смещения числа вправо x раз, а затем выполнения побитового AND ( & ) на нем:

(number >> x) & 1LL;  // 1 if the 'x'th bit of 'number' is set, 0 otherwise

Операция смены вправо может быть реализована как арифметический (подписанный) сдвиг, так и логический (беззнаковый) сдвиг. Если number в number выражения number >> x имеет тип подписи и отрицательное значение, результирующее значение определяется реализацией.

Если нам нужно значение этого бита непосредственно на месте, мы могли бы вместо этого сдвинуть маску:

(number & (1LL << x));  // (1 << x) if the 'x'th bit of 'number' is set, 0 otherwise

Либо можно использовать как условное, так как все ненулевые значения считаются истинными.

Использование std :: bitset

std::bitset<4> num(std::string("0010"));
bool bit_val = num.test(1);  // bit_val value is set to true;

Изменение n-го бита на x

C-стиль бит-манипуляции

// Bit n will be set if x is 1 and cleared if x is 0.
number ^= (-x ^ number) & (1LL << n);

Использование std :: bitset

set(n,val) - устанавливает бит n в значение val .

std::bitset<5> num(std::string("00100"));
num.set(0,true);  // num is now 00101
num.set(2,false); // num is now 00001

Установить все биты

C-стиль бит-манипуляции

x = -1; // -1 == 1111 1111 ... 1111b

^{(См. Здесь, чтобы объяснить, почему это работает и на самом деле лучший подход.)}

Использование std :: bitset

std::bitset<10> x;
x.set(); // Sets all bits to '1'

Снять правый бит

C-стиль бит-манипуляции

template <typename T>
T rightmostSetBitRemoved(T n)
{
    // static_assert(std::is_integral<T>::value && !std::is_signed<T>::value, "type should be unsigned"); // For c++11 and later
    return n & (n - 1);
}

объяснение

• если n равно нулю, то 0 & 0xFF..FF которое равно нулю
• else n может быть записано 0bxxxxxx10..00 а n - 1 - 0bxxxxxx011..11 , поэтому n & (n - 1) равно 0bxxxxxx000..00 .

Набор счетных битов

В криптографии и других приложениях часто требуется подсчет численности битовой строки, и проблема широко изучена.

Наивный способ требует одной итерации на бит:

unsigned value = 1234;
unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (bits = 0; value; value >>= 1)
  bits += value & 1;

Хороший трюк (основанный на « Удалить самый правый бит» ):

unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (; value; ++bits)
  value &= value - 1;

Он проходит через столько итераций , сколько существует набор битов, так что это хорошо , когда value , как ожидается, несколько отличных от нуля бит.

Этот метод был впервые предложен Петром Вегнером (в CACM 3/322 - 1960), и он хорошо известен, так как он появляется на языке программирования C Брайаном Керниганом и Деннисом М. Ричи.

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

unsigned popcount(std::uint64_t x)
{
  const std::uint64_t m1  = 0x5555555555555555;  // binary: 0101...
  const std::uint64_t m2  = 0x3333333333333333;  // binary: 00110011..
  const std::uint64_t m4  = 0x0f0f0f0f0f0f0f0f;  // binary: 0000111100001111

  x -= (x >> 1) & m1;             // put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2); // put count of each 4 bits into those 4 bits 
  x = (x + (x >> 4)) & m4;        // put count of each 8 bits into those 8 bits 
  return (x * h01) >> 56;  // left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

Такая реализация имеет лучшее худшее поведение (см. Вес Хэмминга для получения дополнительной информации).

Многие процессоры имеют определенную инструкцию (например, x86's popcnt ), и компилятор может предложить определенную ( не стандартную ) встроенную функцию. Например, с g ++ есть:

int __builtin_popcount (unsigned x);

Проверьте, является ли целое число мощностью 2

n & (n - 1) трюк (см. « Удалить самый правый бит» ) также полезен для определения того, является ли целое число мощностью 2:

bool power_of_2 = n && !(n & (n - 1));

Обратите внимание, что без первой части проверки ( n && ) 0 неверно считается степенью 2.

Бит-манипулирование Приложение: от малого до крупного письма

Одним из нескольких применений манипуляции бит является преобразование буквы от малого к капиталу или наоборот, выбирая маску и правильную операцию бит . Например, буква имеет это бинарное представление 01(1)00001 , а его капитал аналог имеет 01(0)00001 . Они отличаются только в бит в скобках. В этом случае преобразование письма от маленьких до столицы, в основном установка бита в скобках к одному. Для этого мы делаем следующее:

/****************************************
convert small letter to captial letter.
========================================
     a: 01100001
  mask: 11011111  <-- (0xDF)  11(0)11111
      :---------
a&mask: 01000001  <-- A letter
*****************************************/

Код для преобразования буквы в букву A

#include <cstdio>

int main()
{
    char op1 = 'a';  // "a" letter (i.e. small case)
    int mask = 0xDF; // choosing a proper mask

    printf("a (AND) mask = A\n");
    printf("%c   &   0xDF = %c\n", op1, op1 & mask);
    
    return 0;
}

В результате

$ g++ main.cpp -o test1
$ ./test1
a (AND) mask = A
a   &   0xDF = A