Thao tác bit trong C: Tối ưu hiệu năng với toán tử Bitwise

•

banner

Tóm tắt kiến thức

Toán tử bit là công cụ mạnh mẽ để thao tác ở mức bit, tối ưu hiệu suất và xử lý dữ liệu nhị phân. Hiểu rõ các toán tử bit sẽ giúp bạn viết code hiệu quả hơn và làm việc với hệ thống cấp thấp.

Toán tử bit là những công cụ mạnh mẽ trong lập trình C, cho phép thao tác trực tiếp với các bit của dữ liệu. Mặc dù ít được sử dụng trong lập trình ứng dụng thông thường, nhưng chúng rất quan trọng trong lập trình hệ thống, xử lý dữ liệu nhị phân và tối ưu hóa hiệu suất.

Quảng cáo giúp chúng tôi duy trì trang web này

Tổng quan về toán tử bit

Khái niệm toán tử bit

Toán tử bit thao tác trực tiếp với các bit của dữ liệu, thay vì với giá trị thập phân như các toán tử thông thường. Chúng hoạt động ở mức bit và rất hiệu quả.

Các toán tử bit trong C

Toán tửKý hiệuMô tả
AND&Phép AND bit
OR|Phép OR bit
XOR^Phép XOR bit
NOT~Phép NOT bit
Tại sao toán tử bit quan trọng?
  • Hiệu suất cao: Thao tác trực tiếp với bit, nhanh hơn các phép toán thông thường
  • Tiết kiệm bộ nhớ: Có thể lưu nhiều flag trong một biến
  • Lập trình hệ thống: Cần thiết cho driver, embedded system
  • Mã hóa: Sử dụng trong cryptography và compression

Toán tử AND (&)

Cú pháp và cách hoạt động

kết_quả = toán_hạng_1 & toán_hạng_2;

Toán tử AND trả về 1 chỉ khi cả hai bit đều là 1.

Bảng chân trị AND

Bit 1Bit 2Kết quả
000
010
100
111

Ví dụ:

#include <stdio.h>

int main() {
    int a = 12;  // 1100 in binary
    int b = 10;  // 1010 in binary

    int result = a & b;

    printf("a = %d (binary: 1100)\n", a);
    printf("b = %d (binary: 1010)\n", b);
    printf("a & b = %d (binary: 1000)\n", result);

    return 0;
}

Ứng dụng: Kiểm tra bit chẵn/lẻ

#include <stdio.h>

int isEven(int num) {
    return (num & 1) == 0;
}

int main() {
    int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(numbers) / sizeof(numbers[0]);

    printf("Kiem tra so chan/le:\n");
    for (int i = 0; i < n; i++) {
        printf("%d la so %s\n", numbers[i], isEven(numbers[i]) ? "chan" : "le");
    }

    return 0;
}

Toán tử OR (|)

Cách hoạt động

kết_quả = toán_hạng_1 | toán_hạng_2;

Toán tử OR trả về 1 khi ít nhất một trong hai bit là 1.

Bảng chân trị OR

Bit 1Bit 2Kết quả
000
011
101
111

Ví dụ:

#include <stdio.h>

int main() {
    int a = 12;  // 1100 in binary
    int b = 10;  // 1010 in binary

    int result = a | b;

    printf("a = %d (binary: 1100)\n", a);
    printf("b = %d (binary: 1010)\n", b);
    printf("a | b = %d (binary: 1110)\n", result);

    return 0;
}

Ứng dụng: Bật bit cụ thể

#include <stdio.h>

int setBit(int num, int position) {
    return num | (1 << position);
}

void printBinary(int num) {
    printf("Binary: ");
    for (int i = 7; i >= 0; i--) {
        printf("%d", (num >> i) & 1);
    }
    printf("\n");
}

int main() {
    int num = 8;  // 1000 in binary

    printf("So ban dau: %d\n", num);
    printBinary(num);

    int result = setBit(num, 1);  // Set bit at position 1

    printf("Sau khi set bit 1: %d\n", result);
    printBinary(result);

    return 0;
}

Toán tử XOR (^)

Cách hoạt động

kết_quả = toán_hạng_1 ^ toán_hạng_2;

Toán tử XOR trả về 1 khi hai bit khác nhau.

Bảng chân trị XOR

Bit 1Bit 2Kết quả
000
011
101
110

Ví dụ:

#include <stdio.h>

int main() {
    int a = 12;  // 1100 in binary
    int b = 10;  // 1010 in binary

    int result = a ^ b;

    printf("a = %d (binary: 1100)\n", a);
    printf("b = %d (binary: 1010)\n", b);
    printf("a ^ b = %d (binary: 0110)\n", result);

    return 0;
}

Ứng dụng: Hoán đổi giá trị không dùng biến tạm

#include <stdio.h>

void swapWithoutTemp(int *a, int *b) {
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

int main() {
    int x = 10, y = 20;

    printf("Truoc khi hoan doi: x = %d, y = %d\n", x, y);

    swapWithoutTemp(&x, &y);

    printf("Sau khi hoan doi: x = %d, y = %d\n", x, y);

    return 0;
}

Ứng dụng: Mã hóa đơn giản

#include <stdio.h>
#include <string.h>

void encryptDecrypt(char *str, char key) {
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        str[i] = str[i] ^ key;
    }
}

int main() {
    char message[] = "Hello World";
    char key = 0xAA;  // 10101010 in binary

    printf("Tin nhan goc: %s\n", message);

    // Ma hoa
    encryptDecrypt(message, key);
    printf("Tin nhan da ma hoa: %s\n", message);

    // Giai ma
    encryptDecrypt(message, key);
    printf("Tin nhan da giai ma: %s\n", message);

    return 0;
}

Toán tử NOT (~)

Cách hoạt động

kết_quả = ~toán_hạng;

Toán tử NOT đảo ngược tất cả các bit.

Ví dụ:

#include <stdio.h>

int main() {
    int a = 12;  // 00001100 in binary

    int result = ~a;

    printf("a = %d (binary: 00001100)\n", a);
    printf("~a = %d (binary: 11110011)\n", result);

    return 0;
}

Ứng dụng: Tắt bit cụ thể

#include <stdio.h>

int clearBit(int num, int position) {
    return num & ~(1 << position);
}

int toggleBit(int num, int position) {
    return num ^ (1 << position);
}

void printBinary(int num) {
    printf("Binary: ");
    for (int i = 7; i >= 0; i--) {
        printf("%d", (num >> i) & 1);
    }
    printf("\n");
}

int main() {
    int num = 15;  // 1111 in binary

    printf("So ban dau: %d\n", num);
    printBinary(num);

    int cleared = clearBit(num, 2);  // Clear bit at position 2
    printf("Sau khi clear bit 2: %d\n", cleared);
    printBinary(cleared);

    int toggled = toggleBit(num, 1);  // Toggle bit at position 1
    printf("Sau khi toggle bit 1: %d\n", toggled);
    printBinary(toggled);

    return 0;
}

Toán tử dịch bit (Shift)

Left Shift (<<)

kết_quả = toán_hạng << số_vị_trí;

Dịch tất cả các bit sang trái một số vị trí cụ thể.

Ví dụ Left Shift:

#include <stdio.h>

int main() {
    int a = 5;  // 101 in binary

    printf("a = %d (binary: 101)\n", a);

    int result1 = a << 1;  // 1010 in binary
    printf("a << 1 = %d (binary: 1010)\n", result1);

    int result2 = a << 2;  // 10100 in binary
    printf("a << 2 = %d (binary: 10100)\n", result2);

    return 0;
}

Right Shift (>>)

kết_quả = toán_hạng >> số_vị_trí;

Dịch tất cả các bit sang phải một số vị trí cụ thể.

Ví dụ Right Shift:

#include <stdio.h>

int main() {
    int a = 20;  // 10100 in binary

    printf("a = %d (binary: 10100)\n", a);

    int result1 = a >> 1;  // 1010 in binary
    printf("a >> 1 = %d (binary: 1010)\n", result1);

    int result2 = a >> 2;  // 101 in binary
    printf("a >> 2 = %d (binary: 101)\n", result2);

    return 0;
}

Ứng dụng: Nhân/chia với lũy thừa của 2

#include <stdio.h>

int multiplyByPowerOf2(int num, int power) {
    return num << power;
}

int divideByPowerOf2(int num, int power) {
    return num >> power;
}

int main() {
    int num = 10;

    printf("So goc: %d\n", num);

    printf("Nhan voi 2: %d\n", multiplyByPowerOf2(num, 1));
    printf("Nhan voi 4: %d\n", multiplyByPowerOf2(num, 2));
    printf("Nhan voi 8: %d\n", multiplyByPowerOf2(num, 3));

    printf("Chia cho 2: %d\n", divideByPowerOf2(num, 1));
    printf("Chia cho 4: %d\n", divideByPowerOf2(num, 2));
    printf("Chia cho 8: %d\n", divideByPowerOf2(num, 3));

    return 0;
}

Các hàm tiện ích với bit

Đếm số bit 1

#include <stdio.h>

int countSetBits(int num) {
    int count = 0;
    while (num) {
        count += num & 1;
        num >>= 1;
    }
    return count;
}

int countSetBitsOptimized(int num) {
    int count = 0;
    while (num) {
        num &= (num - 1);  // Loại bỏ bit 1 cuối cùng
        count++;
    }
    return count;
}

int main() {
    int numbers[] = {5, 10, 15, 255};
    int n = sizeof(numbers) / sizeof(numbers[0]);

    printf("Dem so bit 1:\n");
    for (int i = 0; i < n; i++) {
        printf("%d co %d bit 1\n", numbers[i], countSetBitsOptimized(numbers[i]));
    }

    return 0;
}

Tìm bit 1 đầu tiên

#include <stdio.h>

int findFirstSetBit(int num) {
    if (num == 0) return -1;

    int position = 0;
    while (!(num & 1)) {
        num >>= 1;
        position++;
    }
    return position;
}

int main() {
    int numbers[] = {1, 2, 4, 8, 12, 16};
    int n = sizeof(numbers) / sizeof(numbers[0]);

    printf("Tim bit 1 dau tien:\n");
    for (int i = 0; i < n; i++) {
        int pos = findFirstSetBit(numbers[i]);
        printf("%d: bit 1 dau tien o vi tri %d\n", numbers[i], pos);
    }

    return 0;
}

Kiểm tra số có phải lũy thừa của 2

#include <stdio.h>

int isPowerOfTwo(int num) {
    return num > 0 && (num & (num - 1)) == 0;
}

int main() {
    int numbers[] = {1, 2, 4, 8, 16, 32, 64, 128, 100, 200};
    int n = sizeof(numbers) / sizeof(numbers[0]);

    printf("Kiem tra luy thua cua 2:\n");
    for (int i = 0; i < n; i++) {
        printf("%d %s la luy thua cua 2\n", numbers[i],
               isPowerOfTwo(numbers[i]) ? "" : "khong");
    }

    return 0;
}

Ứng dụng thực tế

Quản lý quyền truy cập

#include <stdio.h>

// Các quyền truy cập
#define READ    0x01    // 00000001
#define WRITE   0x02    // 00000010
#define EXECUTE 0x04    // 00000100
#define DELETE  0x08    // 00001000

void grantPermission(int *permissions, int permission) {
    *permissions |= permission;
}

void revokePermission(int *permissions, int permission) {
    *permissions &= ~permission;
}

int hasPermission(int permissions, int permission) {
    return (permissions & permission) != 0;
}

void printPermissions(int permissions) {
    printf("Quyen truy cap: ");
    if (hasPermission(permissions, READ)) printf("READ ");
    if (hasPermission(permissions, WRITE)) printf("WRITE ");
    if (hasPermission(permissions, EXECUTE)) printf("EXECUTE ");
    if (hasPermission(permissions, DELETE)) printf("DELETE ");
    printf("\n");
}

int main() {
    int userPermissions = 0;  // Không có quyền gì

    printf("Ban dau: ");
    printPermissions(userPermissions);

    // Cấp quyền
    grantPermission(&userPermissions, READ);
    grantPermission(&userPermissions, WRITE);

    printf("Sau khi cap quyen: ");
    printPermissions(userPermissions);

    // Thu hồi quyền
    revokePermission(&userPermissions, WRITE);

    printf("Sau khi thu hoi quyen WRITE: ");
    printPermissions(userPermissions);

    return 0;
}

Nén dữ liệu đơn giản

#include <stdio.h>

// Nén 4 số 8-bit thành 1 số 32-bit
unsigned int packFourBytes(unsigned char a, unsigned char b, unsigned char c, unsigned char d) {
    return (a << 24) | (b << 16) | (c << 8) | d;
}

// Giải nén 1 số 32-bit thành 4 số 8-bit
void unpackFourBytes(unsigned int packed, unsigned char *a, unsigned char *b, unsigned char *c, unsigned char *d) {
    *a = (packed >> 24) & 0xFF;
    *b = (packed >> 16) & 0xFF;
    *c = (packed >> 8) & 0xFF;
    *d = packed & 0xFF;
}

int main() {
    unsigned char original[4] = {255, 128, 64, 32};

    printf("Du lieu goc: %d, %d, %d, %d\n",
           original[0], original[1], original[2], original[3]);

    // Nén
    unsigned int packed = packFourBytes(original[0], original[1], original[2], original[3]);
    printf("Du lieu nen: %u\n", packed);

    // Giải nén
    unsigned char unpacked[4];
    unpackFourBytes(packed, &unpacked[0], &unpacked[1], &unpacked[2], &unpacked[3]);
    printf("Du lieu giai nen: %d, %d, %d, %d\n",
           unpacked[0], unpacked[1], unpacked[2], unpacked[3]);

    return 0;
}

Ví dụ thực hành

1. Tìm số bit cần thay đổi để chuyển A thành B

#include <stdio.h>

int countDifferentBits(int a, int b) {
    int xor = a ^ b;
    int count = 0;

    while (xor) {
        count += xor & 1;
        xor >>= 1;
    }

    return count;
}

int main() {
    int a = 10, b = 7;

    printf("So bit can thay doi de chuyen %d thanh %d: %d\n",
           a, b, countDifferentBits(a, b));

    return 0;
}

2. Tìm số bị thiếu trong dãy từ 1 đến n

#include <stdio.h>

int findMissingNumber(int arr[], int n) {
    int total = 0;
    for (int i = 1; i <= n + 1; i++) {
        total ^= i;
    }

    for (int i = 0; i < n; i++) {
        total ^= arr[i];
    }

    return total;
}

int main() {
    int arr[] = {1, 2, 4, 5, 6};  // Thiếu số 3
    int n = sizeof(arr) / sizeof(arr[0]);

    int missing = findMissingNumber(arr, n);
    printf("So bi thieu: %d\n", missing);

    return 0;
}

3. Kiểm tra bit thứ n có được set không

#include <stdio.h>

int isBitSet(int num, int position) {
    return (num >> position) & 1;
}

void printBitPositions(int num) {
    printf("Bit positions cua %d: ", num);
    for (int i = 31; i >= 0; i--) {
        if (isBitSet(num, i)) {
            printf("%d ", i);
        }
    }
    printf("\n");
}

int main() {
    int num = 42;

    printf("Kiem tra bit cua so %d:\n", num);
    for (int i = 0; i < 8; i++) {
        printf("Bit %d: %s\n", i, isBitSet(num, i) ? "SET" : "NOT SET");
    }

    printBitPositions(num);

    return 0;
}

Tổng kết

Toán tử bit là công cụ mạnh mẽ cho lập trình hệ thống và tối ưu hóa hiệu suất ở mức bit.

Lưu ý quan trọng về toán tử bit
  • Endianness: Cẩn thận với byte order khi làm việc với binary data
  • Signed shift: Right shift với số âm có thể có hành vi khác nhau
  • Overflow: Dịch bit quá nhiều có thể gây mất dữ liệu
  • Portability: Một số thao tác có thể khác nhau trên các platform
Best Practices
  • Sử dụng unsigned types khi làm việc với bit
  • Kiểm tra kích thước kiểu dữ liệu trước khi thao tác
  • Sử dụng constants thay vì magic numbers cho bit positions
  • Document rõ ràng các thao tác bit phức tạp

Với những kiến thức này, bạn đã sẵn sàng để làm việc với hệ thống cấp thấp và tối ưu hóa hiệu suất của các chương trình C!

Last updated on

Mảng trong lập trình C: Hướng dẫn toàn diện từ A-Z

Cấu trúc điều khiển trong C: Làm chủ if-else, switch và vòng lặp for, while

On this page

Tổng quan về toán tử bitKhái niệm toán tử bitCác toán tử bit trong CToán tử AND (&)Cú pháp và cách hoạt độngBảng chân trị ANDVí dụ:Ứng dụng: Kiểm tra bit chẵn/lẻToán tử OR (|)Cách hoạt độngBảng chân trị ORVí dụ:Ứng dụng: Bật bit cụ thểToán tử XOR (^)Cách hoạt độngBảng chân trị XORVí dụ:Ứng dụng: Hoán đổi giá trị không dùng biến tạmỨng dụng: Mã hóa đơn giảnToán tử NOT (~)Cách hoạt độngVí dụ:Ứng dụng: Tắt bit cụ thểToán tử dịch bit (Shift)Left Shift (<<)Ví dụ Left Shift:Right Shift (>>)Ví dụ Right Shift:Ứng dụng: Nhân/chia với lũy thừa của 2Các hàm tiện ích với bitĐếm số bit 1Tìm bit 1 đầu tiênKiểm tra số có phải lũy thừa của 2Ứng dụng thực tếQuản lý quyền truy cậpNén dữ liệu đơn giảnVí dụ thực hành1. Tìm số bit cần thay đổi để chuyển A thành B2. Tìm số bị thiếu trong dãy từ 1 đến n3. Kiểm tra bit thứ n có được set khôngTổng kết
Chỉnh sửa trên Github

Tags

# C# Programming# Bitwise# Low Level
avatar

Hoàng Văn Giỏi

Tác giả trang web