Đếm số bước giảm N về 1 theo quy tắc chia 2 hoặc trừ lũy thừa 2 gần nhất C++

Cho số N. Giảm về 1 bằng các bước:

1. Nếu N là lũy thừa của 2: N = N / 2
2. Ngược lại: N = N - 2^⌊log₂(N)⌋ (trừ lũy thừa 2 lớn nhất < N)

Đếm số bước thực hiện.

Ví dụ minh họa

Ví dụ 1: N = 20

20 không phải 2^k → trừ 16 → 4 (bước 1)
4 là 2² → chia 2 → 2 (bước 2)
2 là 2¹ → chia 2 → 1 (bước 3)
Kết quả: 3 bước

Ví dụ 2: N = 32

32→16→8→4→2→1: 5 bước (luôn chia 2)

Mã nguồn C++

#include <iostream>
#include <cmath>
using namespace std;

int stepCount(int n) {
    int count = 0;
    while (n != 1) {
        // Kiểm tra lũy thừa của 2
        if (ceil(log2(n)) == floor(log2(n))) {
            n = n / 2;
        } else {
            int x = floor(log2(n));
            n = n - (int)pow(2, x);
        }
        count++;
    }
    return count;
}

int main() {
    int N = 96;
    cout << "So buoc giam ve 1: " << stepCount(N);
    return 0;
}

Kết quả chạy chương trình

So buoc giam ve 1: 6

Tối ưu hóa - Thao tác bit (O(log N))

Kiểm tra lũy thừa 2: (n & (n-1)) == 0 (với n > 0).

Lũy thừa 2 lớn nhất ≤ n: 1 << (31 - __builtin_clz(n)) (GCC/Clang) hoặc dịch bit.

int stepCountBitwise(int n) {
    int count = 0;
    while (n != 1) {
        if ((n & (n - 1)) == 0) { // Là lũy thừa 2
            n >>= 1; // n = n / 2
        } else {
            // Tìm bit cao nhất = 1
            int msb = 31 - __builtin_clz(n); // GCC/Clang
            // Hoặc: int msb = 0; while ((1 << (msb+1)) <= n) msb++;
            n -= (1 << msb);
        }
        count++;
    }
    return count;
}

Quan sát quy luật (Đếm bit)

Số bước = số bit 1 trong biểu diễn nhị phân của N + vị trí bit cao nhất (0-indexed) - 1.

Ví dụ N=20 (10100₂): bit 1 = 2, msb vị trí 4 → 2 + 4 - 1 = 5? Sai, kết quả thực tế là 3.

Công thức đúng: Mỗi lần trừ 2ᵏ xóa 1 bit 1. Mỗi lần chia 2 dịch phải 1 bit. Tổng bước = (số bit 1 - 1) + (vị trí bit cao nhất).

N=20 (10100): bit 1 = 2, msb=4 → (2-1)+4 = 5? Vẫn sai. Thực tế:

• Trừ 16 (bit 4): 10100 → 00100 (1 bước)
• Chia 2: 00100 → 00010 (1 bước)
• Chia 2: 00010 → 00001 (1 bước)
• Tổng: 3 = (số bit 1) + (msb) - 2? 2+4-2=4. Không.

Cách hiểu đơn giản: Số bước = popcount(N) + floor(log2(N)) - 1.

N=20: popcount=2, log2=4 → 2+4-1=5 ❌

Thử N=20: 10100. Các bước: trừ 2⁴, chia 2, chia 2. = 3.

Công thức: popcount(N-1) + floor(log2(N))?

N=20: N-1=19 (10011), popcount=3, log2=4 → 7 ❌

Kết luận: Dùng vòng lặp bitwise O(log N) là đơn giản và đúng nhất.

Độ phức tạp