Hiểu bài toán

Bài toán yêu cầu xác định tính chẵn lẻ của số lượng bit 1 trong dạng nhị phân của một số nguyên dương N. Cụ thể, với mỗi số N đầu vào, nếu số lượng bit 1 là số chẵn, ta in ra 'even', ngược lại nếu là số lẻ thì in ra 'odd'. Ví dụ: N = 6 (dạng nhị phân là 110) có 2 bit 1 (chẵn) -> in 'even'; N = 7 (dạng nhị phân là 111) có 3 bit 1 (lẻ) -> in 'odd'.

Các cách tiếp cận

Cách Mô phỏng chuyển đổi sang chuỗi nhị phân

#include<bits/stdc++.h>
using namespace std;
string bit(ll n) {
    ll d=0;
    while(n!=1) {
        if(n%2==1) {
            d++;
            n=(n-1)/2;
        }
        else n/=2;
    }
    if(d%2==0)return "odd";
    return "even";
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Tiếp cận này chia đôi liên tục cho 2 để chuyển số sang hệ nhị phân. Với mỗi lần chia, nếu số dư là 1, ta đếm và loại bỏ nó. Sau khi về 1, ta kiểm tra số lượng bit 1 đã đếm được. Tuy nhiên, cách viết này có sai sót: nó không đếm bit cuối cùng (bit 1 của số 1) và logic trả kết quả bị ngược (nếu chẵn lại in 'odd').

Cách Sử dụng hàm h hỗ trợ builtin_popcountll

#include <iostream>
using namespace std;
int main() {
    int t; cin >> t;
    while(t--) {
        long long a; cin >> a;
        long long b = __builtin_popcountll(a);
        cout << ((b % 2) ? "odd\n" : "even\n");
    }
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Sử dụng hàm _builtinpopcountll có sẵn trong GCC để đếm số lượng bit 1 trong 64-bit số nguyên. Hàm này được tối ưu hóa phần cứng (thường là 1 lệnh CPU), chạy cực nhanh. Sau đó chỉ cần kiểm tra tính chẵn lẻ của kết quả.

Cách Tối ưu thuật toán bằng bit counting

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        long long N; cin >> N;
        int cnt = __builtin_popcountll(N);
        if (cnt % 2 == 1) cout << "odd\n";
        else cout << "even\n";
    }
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là cách làm chuẩn và hiệu quả nhất. Code sử dụng _builtinpopcountll để đếm bit 1. Lưu ý về I/O: dùng ios::syncwithstdio(false) và cin.tie(nullptr) để tăng tốc độ nhập xuất. Code chuẩn hóa kết quả đúng theo yêu cầu: bit 1 chẵn -> 'even', bit 1 lẻ -> 'odd'.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán quy về bài toán đếm số bit 1 (population count) trong binary representation của số.
• Sử dụng hàm h _builtinpopcountll là cách hiệu quả nhất (O(1) về mặt lý thuyết thời gian thực thi) thay vì tự implement thuật toán chia đôi.

Lỗi thường gặp

• Lỗi logic trong Solution 1: Quên đếm bit 1 cuối cùng (khi n = 1) và kết quả in ra bị ngược so với yêu cầu.
• Quên xử lý file I/O (freopen) hoặc tối ưu tốc độ nhập xuất (ios_base) làm trễ giờ trong bài toán nhiều test case.