การจัดการบิต (Bit Manipulation) เทคนิคสำคัญใน C++

มาทบทวนเรื่องบิตและบิตวائزออเปอเรเตอร์ (bitwise operators) ให้สั้นๆ กันก่อน

Bit (บิต) คือ ตัวเลขฐานสอง (binary digit) เป็นหน่วยข้อมูลเล็กที่สุดที่คอมพิวเตอร์เข้าใจได้ มีค่าได้เพียง 2 ค่า คือ 0 (ปิด/OFF) และ 1 (เปิด/ON)

บิตวائزออเปอเรเตอร์ คือ โอเปอเรเตอร์ที่ทำงานระดับบิตในโปรแกรม ใช้สำหรับจัดการบิตในโปรแกรม

ใน C เรามีบิตวائزออเปอเรเตอร์ 6 ตัว −

• Bitwise AND (&)
• Bitwise OR (|)
• Bitwise XOR (^)
• Bitwise Left Shift (<<)
• Bitwise Right Shift (>>)
• Bitwise NOT (~)

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

ตอนนี้ มาเรียนรู้เทคนิคสำคัญบางอย่างที่จะช่วยได้ถ้าคุณทำงานกับบิต

สลับค่าตัวเลข 2 ตัว (ใช้ Bitwise XOR)

เราสามารถสลับค่า 2 ตัวได้โดยใช้บิตวائز 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 after swapping!
x = 90    y = 41

วิธีหา MSB (Most Significant Bit) ที่มีประสิทธิภาพ

สำหรับค่าจำนวนเต็มใดๆ เราสามารถหา MSB ได้อย่างมีประสิทธิภาพ โดยใช้ OR operator ร่วมกับบิตวائز shift operator วิธีนี้หา MSB ได้ในเวลา O(1)

ตัวอย่าง

โปรแกรมหา MSB ของจำนวนเต็ม 32-bit −

#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;
        case 2: return n + 1;
        case 3: return 0;
    }
}
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 เท่ากัน โดยตรง

ใช้บิตวائز shift operator สามารถทำได้ง่ายและใช้เวลาน้อย

ตัวอย่าง

#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 นำหน้าและ 0 ต่อท้ายในจำนวนเต็ม

มีฟังก์ชัน built-in สำหรับหาจำนวน leading และ trailing zeros ของจำนวนเต็ม ขอบคุณ bit manipulation

* เป็นฟังก์ชัน built-in ของ 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_ctz(n));
}

เอาต์พุต

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

ตรวจสอบว่าตัวเลขเป็นกำลังของ 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 ของทุก Subset ของเซต

สิ่งนี้ทำได้โดยใช้ข้อเท็จจริงที่ว่า ถ้ามีมากกว่า 1 องค์ประกอบ XOR ของทุก subset จะเป็น 0 เสมอ และเป็นตัวเลขตัวนั้นถ้ามี 1 ตัว

ตัวอย่าง

#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

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

คีย์เวิร์ด auto ใน 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

กลับบิตทั้งหมดของตัวเลข

เราสามารถกลับบิตทั้งหมดของตัวเลขได้โดยการลบออกจากตัวเลขที่บิตทั้งหมดเป็น 1

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 (((result + 1) & result) == 0)
        return 1;
    else
        return 0;
}
int main() {
    int number = 4;
    if (checkBitPattern(number) == 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