การจัดการบิต (กลยุทธ์สำคัญ) ใน C++

เรามาจำเกี่ยวกับบิตกันก่อน และตัวดำเนินการระดับบิตนั้นสั้น

บิต เป็นเลขฐานสอง เป็นหน่วยข้อมูลที่เล็กที่สุดที่คอมพิวเตอร์เข้าใจได้ ในสามารถมีค่าได้เพียงหนึ่งในสองค่า 0 (แสดงว่าปิด) และ 1 (แสดงว่าเปิด) .

ตัวดำเนินการระดับบิต คือโอเปอเรเตอร์ที่ทำงานในระดับบิตในโปรแกรม

โอเปอเรเตอร์เหล่านี้ใช้เพื่อจัดการบิตในโปรแกรม

ใน C เรามีตัวดำเนินการระดับบิต 6 ตัว -

• Bitwise และ (&)

• Bitwise OR (OR)

• Bitwise XOR (XOR)

• Shift ซ้ายระดับบิต (<<)/p>

• เลื่อนไปทางขวาระดับบิต (>>)

• ไม่ระดับบิต (~)

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

ตอนนี้ มาเรียนรู้กลยุทธ์ที่สำคัญบางอย่าง เช่น สิ่งที่จะเป็นประโยชน์หากคุณทำงานกับบิต

สลับสองหมายเลข (โดยใช้ XOR ระดับบิต)

เราสามารถสลับสองค่าโดยใช้ตัวดำเนินการ XOR ระดับบิต การดำเนินการคือ −

ตัวอย่าง

#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 (บิตที่สำคัญที่สุด)

สำหรับค่าจำนวนเต็มใด ๆ เราสามารถหาบิตที่สำคัญที่สุดเป็นวิธีที่มีประสิทธิภาพ ทำได้โดยใช้หรือตัวดำเนินการพร้อมกับตัวดำเนินการกะระดับบิต วิธีนี้สามารถหา MSB ได้ใน o(1) ความซับซ้อนของเวลา

ขนาดของจำนวนเต็มควรถูกกำหนดไว้ล่วงหน้าเพื่อสร้างโปรแกรม

ตัวอย่าง

โปรแกรมค้นหา MSB ของจำนวนเต็ม 32 บิต -

#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

คำนวณ XOR ของตัวเลขทั้งหมดตั้งแต่ 1 ถึง n โดยตรง

ถ้าเราสังเกต XOR ของ 0 ถึง n อย่างระมัดระวัง เราก็จะได้รูปแบบทั่วไป ซึ่งมีภาพประกอบอยู่ที่นี่ -

ตัวอย่าง

#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 นั้นทำได้ง่ายหรือไม่โดยใช้ตัวดำเนินการระดับบิต

ตัวอย่าง

#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 ของเซตย่อยทั้งหมดของเซต

ซึ่งสามารถทำได้โดยใช้ข้อเท็จจริงที่ว่าหากมีองค์ประกอบมากกว่า 1 รายการ 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

การแปลงเลขฐานสองของจำนวนเต็มที่กำหนด

อัตโนมัติ มีการใช้คีย์เวิร์ดในภาษา 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