Việc đếm số bit 1 trong biểu diễn nhị phân của một số nguyên là thao tác cơ bản trong lập trình hệ thống, tối ưu thuật toán và xử lý dữ liệu. Dưới đây là cách tiếp cận hiệu quả cùng các ứng dụng thực tế.

1. Đếm bit 1 bằng phép AND với (n - 1)

Phương pháp này tận dụng tính chất: n & (n - 1) sẽ xóa đi bit 1 ở vị trí thấp nhất của n. Lặp lại đến khi n về 0, số lần lặp chính là số bit 1.

int countBits(int num) {
    int total = 0;
    while (num) {
        num &= (num - 1);
        total++;
    }
    return total;
}

2. Tính lũy thừa nhanh bằng chia để trị

Thay vì nhân lặp, ta dùng kỹ thuật "fast exponentiation" dựa trên biểu diễn nhị phân của số mũ. Mỗi bit 1 trong số mũ tương ứng với một phép nhân vào kết quả.

double fastPow(double base, int exp) {
    if (exp == 0) return 1.0;
    if (base == 0.0) return (exp > 0) ? 0.0 : INFINITY;

    double result = 1.0;
    double current = (exp < 0) ? 1.0 / base : base;
    unsigned int absExp = (exp < 0) ? -exp : exp;

    while (absExp > 0) {
        if (absExp & 1) result *= current;
        current *= current;
        absExp >>= 1;
    }
    return result;
}

3. Sắp xếp mảng: số lẻ trước, số chẵn sau

Dùng hai con trỏ từ hai đầu mảng, hoán đổi khi phát hiện số chẵn bên trái và số lẻ bên phải, cho đến khi hai con trỏ gặp nhau.

void arrangeOddEven(int arr[], int len) {
    int left = 0, right = len - 1;
    while (left < right) {
        while (left < right && arr[left] % 2 != 0) left++;
        while (left < right && arr[right] % 2 == 0) right--;
        if (left < right) {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
        }
    }
}

4. Tìm phần tử thứ k từ cuối danh sách liên kết

Sử dụng hai con trỏ: con trỏ nhanh đi trước k bước, sau đó cả hai cùng di chuyển. Khi con trỏ nhanh đến cuối, con trỏ chậm sẽ ở vị trí cần tìm.

struct Node* findKthFromEnd(struct Node* head, int k) {
    if (!head || k <= 0) return NULL;
    
    struct Node *fast = head, *slow = head;
    
    for (int i = 0; i < k; i++) {
        if (!fast) return NULL;
        fast = fast->next;
    }
    
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    
    return slow;
}

5. Đảo ngược danh sách liên kết

Cập nhật con trỏ next của mỗi node để trỏ ngược lại node trước đó, sử dụng ba con trỏ để theo dõi vị trí hiện tại, trước và sau.

struct Node* reverseLinkedList(struct Node* head) {
    struct Node *prev = NULL, *current = head, *nextNode;
    
    while (current) {
        nextNode = current->next;
        current->next = prev;
        prev = current;
        current = nextNode;
    }
    
    return prev;
}