C++
Bitmanipulation

Anmärkningar

#include <bitset>

Ställer in lite

C-stil bitmanipulation

En bit kan ställas in med bitvis OR-operatören ( | ).

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

Använda std :: bitset

set(x) eller set(x,true) - sätter biten i position x till 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

Rensa lite

C-stil bitmanipulation

En bit kan rensas med bitvis OCH-operatören ( & ).

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

Använda std :: bitset

reset(x) eller set(x,false) - rensar biten i position 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

Växlar lite

C-stil bitmanipulation

Lite kan växlas med XOR-operatören ( ^ ).

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

Använda 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)

Kolla lite

C-stil bitmanipulation

Värdet på biten kan erhållas genom att flytta numret till höger x gånger och sedan utföra bitvis OCH ( & ) på den:

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

Högerväxlingsoperationen kan implementeras som antingen en aritmetisk (signerad) skift eller en logisk (osignerad) skift. Om number i uttrycksnumret number >> x har en signerad typ och ett negativt värde, är det resulterande värdet implementeringsdefinerat.

Om vi behöver värdet på den biten direkt på plats kan vi istället lämna masken:

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

Endera kan användas som villkorat, eftersom alla icke-nollvärden betraktas som sanna.

Använda std :: bitset

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

Ändra den nionde biten till x

C-stil bitmanipulation

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

Använda std :: bitset

set(n,val) - sätter bit n till värdet val .

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

Ställ in alla bitar

C-stil bitmanipulation

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

^{(Se här för en förklaring av varför detta fungerar och är den bästa metoden.)}

Använda std :: bitset

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

Ta bort biten längst till höger

C-stil bitmanipulation

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

Förklaring

• om n är noll, har vi 0 & 0xFF..FF vilket är noll
• annars kan n skrivas 0bxxxxxx10..00 och n - 1 är 0bxxxxxx011..11 , så n & (n - 1) är 0bxxxxxx000..00 .

Räkna bitar inställda

Befolkningsantalet för en bitsträng behövs ofta i kryptografi och andra applikationer och problemet har studerats i stor utsträckning.

Det naiva sättet kräver en iteration per 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;

Ett trevligt trick (baserat på Ta bort högst uppsatta bit ) är:

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

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

Det går igenom så många iterationer som det finns inställda bitar, så det är bra när value förväntas ha få bitar utan noll.

Metoden föreslogs först av Peter Wegner (i CACM 3/322 - 1960) och den är välkänd eftersom den visas i C Programming Language av Brian W. Kernighan och Dennis M. Ritchie.

Detta kräver 12 aritmetiska operationer, varav en är en multikation:

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

Den här typen av implementering har det bästa värsta fallet (se Hamming-vikt för mer information).

Många processorer har en specifik instruktion (som x86: s popcnt ) och kompilatorn kan erbjuda en specifik ( icke standard ) inbyggd funktion. Exempelvis med g ++ finns det:

int __builtin_popcount (unsigned x);

Kontrollera om ett heltal är en effekt på 2

n & (n - 1) tricket (se Ta bort den högsta inställda biten ) är också användbart för att avgöra om ett heltal är en effekt på 2:

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

Observera att utan den första delen av kontrollen ( n && ) betraktas 0 felaktigt som en effekt på 2.

Ansökan om bitmanipulation: liten till stor bokstav

En av flera tillämpningar av bitmanipulation är att konvertera en bokstav från liten till stor eller vice versa genom att välja en mask och en korrekt bitoperation . Till exempel, ett brev har detta binär representation 01(1)00001 medan dess kapital motsvarighet har 01(0)00001 . De skiljer sig endast i biten inom parentes. I det här fallet sätter konversationen av en bokstav från liten till stor bokstav i grunden biten inom parentes till en. För att göra det gör vi följande:

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

Koden för konvertering av ett brev till ett brev är

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

Resultatet är

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