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 스타일 비트 조작

비트는 비트 AND 연산자 ( & )를 사용하여 지울 수 있습니다.

// 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 >> x 서명 유형 및 음의 값을 가지며, 그 결과 값은 구현 정의된다.

우리가 그 비트의 값을 직접적으로 필요로한다면, 대신 마스크를 옮길 수 있습니다 :

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

0이 아닌 값이 모두 참으로 간주되므로 조건부로 사용할 수 있습니다.

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이면 우리는 0 & 0xFF..FF 를 가지며 0입니다.
• 그렇지 않으면 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 이 0이 아닌 비트가 거의 없을 것으로 예상 될 때 좋습니다.

이 방법은 Peter Wegner ( CACM 3 / 322-1960)에 의해 처음 제안되었으며 Brian W. Kernighan과 Dennis M. Ritchie의 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) + ... 
}

이러한 종류의 구현은 최상의 최악의 경우 동작을합니다 (자세한 내용은 해밍 웨이트 참조).

많은 CPU가 특정 명령 (예 : x86의 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