C ++でのビット操作（重要な戦術）

---

最初にaboutビットを思い出してみましょう。ビット演算子は短いです。

ビット 2進数です。これは、コンピューターが理解できるデータの最小単位です。 Inは、 0（オフを示す）と1（オンを示す）の2つの値のうちの1つのみを持つことができます。 。

ビット演算子 プログラムでビットレベルで動作する演算子です。

これらの演算子は、プログラムのビットを操作するために使用されます。

Cには、6つのビット演算子があります-

• ビットごとのAND（＆）

• ビットごとのOR（OR）

• ビットごとのXOR（XOR）

• ビット単位の左Shift（<<）/ p>

• ビット単位の右シフト（>>）

• ビット単位ではありません（〜）

https://www.tutorialspoint.com/cprogramming/c_bitwise_operators.htm

それでは、いくつかの重要な戦術、つまり、ビットを操作する場合に役立つ可能性のあるものを学びましょう。

2つの数値を入れ替えます（ビット単位のXORを使用）

ビット単位のXOR演算子を使用して2つの値を交換できます。実装は-

です

例

#include <stdio.h>
int main(){
   int x = 41;
   int y = 90;
   printf("Values before swapping! \n");
   printf("x = %d \t", x);
   printf("y = %d \n", y);
   x = x ^ y;
   y = y ^ x;
   x = x ^ y;
   printf("Values after swapping! \n");
   printf("x = %d \t", x);
   printf("y = %d \n", y);
   return 0;
}

出力

Values before swapping!
x = 41 y = 90
Values before swapping!
x = 90 y = 41

MSB（最上位ビット）を見つける効率的な方法

どの整数値でも、最上位ビットが効果的な方法であることがわかります。これは、ビット単位のシフト演算子とともにor演算子を使用して行われます。このメソッドは、o（1）時間計算量でMSBを見つけることができます。

プログラムを作成するには、整数のサイズを事前に定義する必要があります。

例

32ビット整数のMSBを見つけるプログラム-

#include <stdio.h>
int findMSB(int x){
   x |= x>>1;
   x |= x>>2;
   x |= x>>4;
   x |= x>>8;
   x |= x>>16;
   x = x+1;
   return(x >> 1);
}
int main(){
   int x = 49;
   printf("The number is %d\n", x);
   int msb = findMSB(x);
   printf("MSB of the number is %d\n", msb);
}

出力

The number is 49
MSB of the number is 32

1からnまでのすべての数値のXORを直接計算します。

0からnのXORを注意深く観察すると、一般的なパターンを導き出すことができます。ここに示されている-

例

#include <stdio.h>
// Direct XOR of all numbers from 1 to n
int findXORuptoN(int n){
   switch( n%4){
      case 0: return n;
      case 1: return 1;
      break;
      case 2: return n+1;
      break;
      case 3: return 0;
      break;
      default: break;
   }
}
int main(){
   int n = 9870;
   int xorupton = findXORuptoN(n);
   printf("XOR of all number up to %d is %d\n", n, xorupton);
}

出力

XOR of all number up to 9870 is 9871

合計とXORが等しい数で、以下の数の組み合わせの総数を直接計算します。

ビット単位のシフト演算子を使用すると、作業を簡単に行うことができ、必要な時間も短くなります。

例

#include <stdio.h>
int countValues(int n){
   int unset=0;
   while (n){
      if ((n & 1) == 0)
         unset++;
      n=n>>1;
   }
   return (1<<unset);
}
int main(){
   int n = 32;
   printf("%d", countValues(n));
}

出力

32

整数の先頭と末尾の0の数を見つける

ビット操作のおかげで、整数の先頭と末尾のゼロの数を見つけるための組み込みのメソッドがあります。

*これはGCC組み込み関数です

例

#include <stdio.h>
int main(){
   int n = 32;
   printf("The integer value is %d\n", n);
   printf("Number of leading zeros is %d\n", __builtin_clz(n));
   printf("Number of trailing zeros is %d\n",__builtin_clz(n));
}

出力

The integer value is 32
Number of leading zeros is 26
Number of trailing zeros is 26

数値が2の累乗であるかどうかを確認しますか？

数値が2の累乗であるかどうかを確認するには、ビット演算子を使用すると簡単になります。

例

#include <stdio.h>
int isPowerof2(int n){
   return n && (!(n&(n-1)));
}
int main(){
   int n = 22;
   if(isPowerof2(n))
      printf("%d is a power of 2", n);
   else
      printf("%d is not a power of 2", n);
}

出力

22 is not a power of 2

セットのすべてのサブセットのXORを検索

これは、複数の要素がある場合、すべてのサブセットのXORが常に0であり、それ以外の場合はその数であるという事実を使用して行うことができます。

例

#include <stdio.h>
int findsubsetXOR (int set[], int size){
   if (size == 1){
      return set[size - 1];
   }
   else
      return 0;
}
int main (){
   int set[] = { 45, 12 };
   int size = sizeof (set) / sizeof (set[0]);
   printf ("The XOR of all subsets of set of size %d is %d\n", size,
   findsubsetXOR (set, size));
   int set2[] = { 65 };
   size = sizeof (set2) / sizeof (set2[0]);
   printf ("The XOR of all subsets of set of size %d is %d\n", size,
   findsubsetXOR (set2, size));
}

出力

The XOR of all subsets of set of size 2 is 0
The XOR of all subsets of set of size 1 is 65

指定された整数の2進数を変換するには

自動 タスクを実行するためにCのキーワードが使用されます。

例

#include <stdio.h>
int main (){
   auto integer = 0b0110110;
   printf("The integer conversion of binary number '0110110' is %d", integer);
}

出力

The integer conversion of binary number '0110110' is 54

数値のすべてのビットを反転する

すべてのビットが設定されている数値から減算することで、数値のすべてのビットを反転できます。

Number = 0110100
The number will all bits set = 1111111
Subtraction -> 1111111 - 0110100 = 1001011 (number with flipped bits)

例

#include <stdio.h>
int main (){
   int number = 23;
   int n = number;
   n |= n>>1;
   n |= n>>2;
   n |= n>>4;
   n |= n>>8;
   n |= n>>16;
   printf("The number is %d\n", number);
   printf("Number with reversed bits %d\n", n-number);
}

出力

The number is 23
Number with reversed bits 8

ビットに代替パターンがあるかどうかを確認する

ビット単位のXOR演算を使用して、数値のビットが代替パターンであるかどうかを確認できます。以下のコードは、次の方法を示しています-

例

#include <stdio.h>
int checkbitpattern(int n){
   int result = n^(n>>1);
   if(((n+1)&n) == 0)
      return 1;
   else
      return 0;
}
int main (){
   int number = 4;
   if(checkbitpattern == 1){
      printf("Bits of %d are in alternate pattern", number);
   }
   else
      printf("Bits of %d are not in alternate pattern", number);
}

出力

Bits of 4 are not in alternate pattern