Trong các hệ thống phân tán xử lý sự kiện bất đồng bộ, làm thế nào để xác định xem một số nguyên 32-bit có phải là lũy thừa của 2 (Power of Two) hay không bằng kỹ thuật Bit Manipulation nhằm tối ưu hóa hiệu năng kiểm tra kích thước bộ đệm?

Question

Accepted Answer

Bản chất vấn đề
Trong lập trình hệ thống và các ứng dụng Enterprise xử lý buffer, kích thước của bộ đệm thường phải là lũy thừa của 2 để tối ưu hóa việc phân bổ bộ nhớ và tính toán địa chỉ. Việc dùng các vòng lặp hoặc phép toán chia lấy dư (modulo) sẽ làm giảm hiệu năng đáng kể.
Giải pháp tối ưu với Bitwise Operators
Một số nguyên dương n là lũy thừa của 2 khi và chỉ khi biểu diễn nhị phân của nó chỉ chứa duy nhất một bit 1. 
Khi trừ số đó đi 1 (n - 1), tất cả các bit kể từ bit 1 thấp nhất trở về bên phải sẽ bị đảo ngược (từ 0 thành 1, từ 1 thành 0), và bit 1 ban đầu trở thành 0. Do đó, phép toán n & (n - 1) sẽ triệt tiêu hoàn toàn bit 1 duy nhất đó.
Ví dụ cài đặt mã nguồn (Java/C#)
public class PowerOfTwoChecker {
    public static boolean isPowerOfTwo(int n) {
        // Phải đảm bảo n > 0 vì số âm và 0 không phải là lũy thừa của 2
        return n > 0 && (n & (n - 1)) == 0;
    }
}
Phân tích chuyên sâu Enterprise

Time Complexity: O(1) tuyệt đối vì chỉ thực hiện một phép so sánh logic và một phép toán bitwise AND.
Space Complexity: O(1) không cấp phát thêm bộ nhớ.
Lưu ý thực chiến: Cần kiểm tra kỹ điều kiện biên khi n <= 0. Nếu truyền vào số 0, biểu thức 0 & -1 trả về 0, dẫn đến kết quả sai nếu thiếu điều kiện n > 0.

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi bit manipulation liên quan cùng chủ đề