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

すべての非ゼロ値は真とみなされるので、いずれかを条件として使用できます。

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値は0です
• そうでなければnは0bxxxxxx10..00と書くことができ、 n - 1は0bxxxxxx011..11 、 n & (n - 1)は0bxxxxxx000..00 。

カウントビット数の設定

ビットストリングの人口数は、暗号化やその他のアプリケーションでしばしば必要とされ、この問題は広く研究されています。

ナイーブな方法では、ビットごとに1回の反復が必要です。

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

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

素敵なトリック（ Remove rightmost set bitに基づいて）：

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

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

それは、設定されたビット数と同じくらい多くの繰り返しを経るので、 valueが非ゼロビットをほとんど持たないvalueが期待されるときは良いことです。

この方法はPeter Wegner（ CACM 3 / 322-1960）が最初に提案したものであり、Brian W. KernighanとDennis M. RitchieのCプログラミング言語に登場して以来、よく知られています。

これには12の算術演算が必要で、そのうちの1つは多項式です。

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の累乗とみなされます。

ビット操作アプリケーション：大文字小文字

ビット操作のいくつかのアプリケーションの1つは、 マスクと適切なビット操作を選択することによって、文字を小から大に、またはその逆に変換することです。たとえば、文字はこの2進表現01(1)00001を持ち、大文字の対応は01(0)00001です。それらは括弧内のビットだけで異なる。この場合、小文字から大文字への変換は、基本的に括弧内のビットを1に設定することです。そうするために、私たちは次のことを行います：

/****************************************
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