C++
Manipulacja bitami

Uwagi

#include <bitset>

Ustawienie trochę

Manipulowanie bitami w stylu C.

Bit można ustawić za pomocą bitowego operatora OR ( | ).

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

Używanie std :: bitset

set(x) lub set(x,true) - ustawia bit w pozycji x na 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

Trochę się wyczyściłem

Manipulowanie bitami w stylu C.

Bit można wyczyścić za pomocą bitowego operatora AND ( & ).

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

Używanie std :: bitset

reset(x) lub set(x,false) - usuwa bit w pozycji 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

Trochę się przełączam

Manipulowanie bitami w stylu C.

Trochę można przełączać za pomocą operatora XOR ( ^ ).

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

Używanie 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)

Trochę sprawdzam

Manipulowanie bitami w stylu C.

Wartość bitu można uzyskać, przesuwając liczbę w prawo x razy, a następnie wykonując bitowe AND ( & ) na niej:

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

Operacja przesunięcia w prawo może być zaimplementowana jako przesunięcie arytmetyczne (ze znakiem) lub przesunięcie logiczne (bez znaku). Jeśli number w wyrażeniu number >> x ma typ ze znakiem i wartość ujemną, wynikowa wartość jest definiowana implementacyjnie.

Jeśli potrzebujemy wartości tego bitu bezpośrednio w miejscu, możemy zamiast tego przesunąć maskę w lewo:

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

Można użyć dowolnego z nich jako warunkowego, ponieważ wszystkie niezerowe wartości są uważane za prawdziwe.

Używanie std :: bitset

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

Zmiana n-tego bitu na x

Manipulowanie bitami w stylu C.

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

Używanie std :: bitset

set(n,val) - ustawia bit n na wartość val .

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

Ustaw wszystkie bity

Manipulowanie bitami w stylu C.

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

^{(Zobacz tutaj wyjaśnienie, dlaczego to działa i jest właściwie najlepszym podejściem).}

Używanie std :: bitset

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

Usuń ustawiony prawy bit

Manipulowanie bitami w stylu 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);
}

Wyjaśnienie

• jeśli n wynosi zero, mamy 0 & 0xFF..FF które jest zerowe
• w przeciwnym razie n można zapisać 0bxxxxxx10..00 a n - 1 to 0bxxxxxx011..11 , więc n & (n - 1) to 0bxxxxxx000..00 .

Liczenie bitów ustawione

Liczba populacji ciągów bitów jest często potrzebna w kryptografii i innych aplikacjach, a problem został szeroko przebadany.

Naiwny sposób wymaga jednej iteracji na bit:

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

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

Fajna sztuczka (oparta na bicie Usuń prawy ustawiony bit ) to:

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

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

Przechodzi tyle iteracji, ile jest ustawionych bitów, więc dobrze, gdy value ma mieć kilka niezerowych bitów.

Metoda została po raz pierwszy zaproponowana przez Petera Wegnera (w CACM 3/322 - 1960) i jest dobrze znana, ponieważ pojawia się w języku programowania C przez Briana W. Kernighana i Dennisa M. Ritchiego.

Wymaga to 12 operacji arytmetycznych, z których jedna jest mnożeniem:

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) + ... 
}

Ten rodzaj implementacji ma najlepsze zachowanie w najgorszym przypadku (więcej szczegółów znajduje się w części Hamminga ).

Wiele procesorów ma określoną instrukcję (np. popcnt x86), a kompilator może oferować określoną ( niestandardową ) funkcję wbudowaną. Np. Z g ++ jest:

int __builtin_popcount (unsigned x);

Sprawdź, czy liczba całkowita jest potęgą 2

Sztuczka n & (n - 1) (zobacz Usuwanie najbardziej ustawionego bitu po prawej ) jest również przydatna do ustalenia, czy liczba całkowita jest potęgą 2:

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

Zauważ, że bez pierwszej części czeku ( n && ) 0 jest niepoprawnie uważane za potęgę 2.

Aplikacja do manipulacji bitami: od małej do dużej litery

Jednym z kilku zastosowań manipulacji bitami jest konwersja litery z małej na dużą lub odwrotnie poprzez wybranie maski i odpowiedniej operacji bitowej . Na przykład, list ma ten binarną reprezentację 01(1)00001 , podczas gdy jego odpowiednik kapitał ma 01(0)00001 . Różnią się one jedynie odrobiną w nawiasach. W takim przypadku konwersja litery z małej na dużą w zasadzie powoduje ustawienie bitu w nawiasach na jeden. Aby to zrobić, wykonujemy następujące czynności:

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

Kod do konwersji litery na literę A to

#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;
}

Wynik to

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