Thuật toán C/C++

Thao tác bit

Bit mask biểu diễn gọn nhiều option boolean trong unsigned integer.

Thao tác bit là gì?

Bit mask biểu diễn gọn nhiều option boolean trong unsigned integer.

Set, clear, toggle và test từng flag.

Điểm quan trọng

Test input rỗng, một phần tử, trùng lặp và đã sắp xếp.
Tách correctness khỏi optimization.
Ưu tiên standard library trong code production.

Code ví dụ bằng C và C++

Chạy code →

main.c

#include <stdio.h>

int main(void) {
    unsigned flags = 0;
    flags |= 1u << 1;
    flags |= 1u << 3;
    flags ^= 1u << 1;
    printf("flags=%u bit3=%u\n", flags, (flags >> 3) & 1u);
}

Output dự kiến

flags=8 bit3=1

C++

Chạy code →

main.cpp

#include <bitset>
#include <iostream>

int main() {
    std::bitset<4> flags;
    flags.set(1);
    flags.set(3);
    flags.flip(1);
    std::cout << "flags=" << flags
              << " bit3=" << flags.test(3) << '\n';
}

Output dự kiến

flags=1000 bit3=1

So sánh C và C++

Dùng unsigned type để shift dự đoán được; C thao tác integer mask, C++ bitset có method rõ nghĩa và output binary dễ đọc.

Loop, pointer, length và buffer tạm được viết tường minh.

C++

Iterator và standard algorithm tách operation khỏi cách lưu dữ liệu.

Bài tập mở rộng

Chạy cả hai phiên bản rồi thay đổi để quan sát khác biệt về bảo đảm của từng ngôn ngữ.

Trace từng phép so sánh trên giấy.
Test duplicate và extreme value.
Benchmark code tự viết với standard library.