Hoán vị 2 số trong C/C++ (nhiều phương án)

Hoán vị 2 số là kỹ thuật căn bản xuất hiện trong hầu hết thuật toán như sắp xếp, xử lý mảng hay thao tác bit. Ví dụ thực tế:

• Đảo vị trí phần tử trong thuật toán tìm kiếm nổi bọt (bubble sort).
• Hoán đổi node trong danh sách liên kết.
• Tối ưu hóa thao tác với register trong embedded systems.

Các phương pháp hoán vị 2 số

1. Dùng biến tạm (Tiêu chuẩn)

Mình thường nghĩ về việc đổi nước trong cốc A và cốc B cho nhau khi cài đặt hoán vị 2 số theo cách này, bằng việc sử dụng thêm cốc C không đựng nước.

void swapTemp(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

Ưu điểm:

• Dễ đọc, hoạt động với mọi kiểu dữ liệu
• Tốc độ nhanh (3 phép gán)
• Thread-safe và không có rủi ro biên

Ứng dụng:

• Thích hợp cho 99% trường hợp thực tế
• Được sử dụng rộng rãi trong thư viện chuẩn và các framework

// Ví dụ thực tế trong thuật toán Bubble Sort
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Hoán vị arr[j] và arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

2. Phép toán Số học

void swapArithmetic(int &a, int &b) {
    // Cảnh báo: Có thể tràn số với giá trị lớn
    a = a + b;
    b = a - b; // => (a+b)-b = a
    a = a - b; // => (a+b)-a = b
}

Lưu ý quan trọng:

• Nguy cơ tràn số: Nếu tổng a+b > INT_MAX, sẽ xảy ra lỗi tràn số
• Không dùng cho số thực (do sai số làm tròn)
• Không hiệu quả với kiểu dữ liệu lớn

Cách an toàn hơn:

// Kiểm tra tràn số trước khi thực hiện
if ((a < 0 && b > 0 && a < INT_MIN + b) || 
    (a > 0 && b > 0 && a > INT_MAX - b)) {
    // Dùng phương pháp biến tạm khi có nguy cơ tràn số
    int temp = a;
    a = b;
    b = temp;
} else {
    a = a + b;
    b = a - b;
    a = a 

3. Phép XOR (Bitwise)

void swapXOR(int &a, int &b) {
    // QUAN TRỌNG: Chỉ hoạt động khi a và b có địa chỉ bộ nhớ khác nhau
    if (&a != &b) { // Kiểm tra rất quan trọng!
        a = a ^ b; // Bitmask khác biệt
        b = a ^ b; // => (a^b)^b = a
        a = a ^ b; // => (a^b)^a = b
    }
}

Giải thích:
Mỗi phép XOR hoạt động như “khóa” để lấy thông tin:

Ban đầu: a = 5 (0101), b = 3 (0011)
Bước 1: a = 0101 ^ 0011 = 0110 (6)
Bước 2: b = 0110 ^ 0011 = 0101 (5)
Bước 3: a = 0110 ^ 0101 = 0011 (3)

Cảnh báo quan trọng:
Hoán vị 2 số sử dụng XOR sẽ gây lỗi nghiêm trọng khi a và b tham chiếu đến cùng một biến. Ví dụ:

int arr[5] = {1, 2, 3, 4, 5};
swapXOR(arr[2], arr[2]); // Thảm họa! Sẽ biến arr[2] thành 0

Khi a và b cùng địa chỉ, quá trình diễn ra:

a = a ^ a = 0; // XOR với chính nó luôn bằng 0
b = 0 ^ b = b; // Không thay đổi
a = 0 ^ b = b; // a và b giờ đều bằng b, mất giá trị ban đầu

### 4. Dùng hàm trong thư viện STL (C++ Tiêu chuẩn)

Dùng thư viện để hoán vị 2 số thật sự nhàn hơn rất nhiều, và nó cũng có ưu điểm hơn. Bạn hoàn toàn nên dùng khi đã nắm vững kiến thức.

#include <algorithm>
std::swap(a, b); // Template hoạt động với mọi kiểu

Sử dụng STL tối ưu hơn và nó sử dụng move semantics:

• Nhiều compiler tối ưu thành lệnh assembly XCHG với kiểu dữ liệu nguyên thủy
• Sử dụng Move Semantics để tối ưu hoán đổi với kiểu dữ liệu phức tạp

// Bên trọng của std::swap trong C++11 trở lên
template<class T>
void swap(T& a, T& b) {
    T temp = std::move(a); // Move thay vì copy
    a = std::move(b);      // Hiệu quả với đối tượng lớn
    b = std::move(temp);
}

Ví dụ với đối tượng lớn:

// Hoán vị hai vector lớn
std::vector<int> v1(10000, 1);  // Vector 10.000 phần tử = 1
std::vector<int> v2(10000, 2);  // Vector 10.000 phần tử = 2

std::swap(v1, v2);  // Rất hiệu quả, chỉ trao đổi pointer nội bộ

Với C++ 17 trở lên, bạn cũng có thể sử dụng exchange function:

b = std::exchange(a, b);
// Lệnh trên tương đương với:
auto old_a = a;
a = b;
b = old_a;

So sánh các phương pháp hoán vị

Dưới đây là bảng so sánh (tham khảo) các phương pháp hoán vị theo các tiêu chí thời gian, kiểu dữ liệu hỗ trợ, mức sử dụng bộ nhớ, và tính an toàn khi dùng trong multi-thread.

(Test trên GCC 10.2 với -O3, Intel i7-9700K)

¹ XOR swap không thread-safe nếu biến có thể bị thay đổi bởi thread khác giữa các bước XOR.

Benchmark với đối tượng phức tạp:

Khi nào nên sử dụng?

Biến tạm (Tiêu chuẩn)

• Khi nào dùng: Mọi tình huống, đặc biệt là code cần bảo trì
• Ví dụ: Các thuật toán sắp xếp, thao tác trên mảng

Phép toán Số học

• Khi nào dùng: Hệ thống nhúng với bộ nhớ hạn chế, giá trị số nhỏ
• Ví dụ: Đảo biến trong vi điều khiển 8-bit

Phép XOR

• Khi nào dùng: Embedded systems, tối ưu assembly, phỏng vấn
• Ví dụ: Swap register trong lập trình hệ thống

std::swap

• Khi nào dùng: Sử dụng STL, đối tượng phức tạp, code sản phẩm
• Ví dụ: Hoán vị container như vector, map, string

std::exchange

• Khi nào dùng: C++17, code sạch, tối ưu tốc độ
• Ví dụ: Triển khai các cấu trúc dữ liệu hiện đại

FAQ – Các câu hỏi thường gặp

1. Tại sao không nên dùng XOR swap trong code sản phẩm?

XOR swap khó đọc, dễ gây lỗi khi a và b cùng địa chỉ, và thường không nhanh hơn std::swap. Hầu hết compiler hiện đại sẽ tối ưu std::swap thành assembly tương tự hoặc tốt hơn.

2. Nếu cần tối ưu tối đa, nên dùng phương pháp nào?

Cho code sản phẩm, hãy dùng std::swap và để compiler tối ưu. Với embedded systems cực kỳ hạn chế, XOR swap có thể phù hợp nếu bạn hiểu rõ các rủi ro.

3. Hoán vị in-place có ý nghĩa gì?

Hoán vị in-place là phương pháp không dùng thêm bộ nhớ (như XOR swap hoặc phép toán số học). Tuy nhiên, với CPU hiện đại, việc tiết kiệm một biến tạm thường không quan trọng bằng tính đọc hiểu của code.

Kết luận

• ✅ Người mới: Dùng biến tạm, hoặc std::swap
• ⚡ Tối ưu: std::swap thường được compiler tối ưu tốt nhất
• 🔥 Thử thách: Dùng XOR cho hệ thống nhúng hoặc bài phỏng vấn
• 🚀 Modern C++: Cân nhắc std::exchange khi cần code ngắn gọn

Câu hỏi thảo luận

• Bạn đã gặp tình huống nào mà phương pháp thông thường không hoạt động?
• Có cách nào hoán vị 2 số chỉ bằng 1 dòng lệnh C++?

Hãy chia sẻ cách tiếp cận của bạn ở phần bình luận! Đừng quên thử nghiệm với Compiler Explorer để xem mã assembly tương ứng.