In các bước biến số thành dạng 2^X - 1 trong C

Cho số n, in ra các bước biến đổi số này thành dạng 2^X - 1 bằng phép XOR.

• Bước lẻ: XOR số với 2^M - 1 (M do bạn chọn).
• Bước chẵn: Tăng số lên 1.

Lặp lại cho đến khi số có dạng 2^X - 1, in tất cả các bước.

Ví dụ

Input: 22
Output:
Step 1: Xor with 15
Step 2: Increase by 1
Step 3: Xor with 7
Step 4: Increase by 1
Step 5: Xor with 1

Input: 7
Output: No Steps to be performed

Thuật toán

int find_leftmost_unsetbit(int n)
BẮT ĐẦU
BƯỚC 1: ind = -1, i = 1
BƯỚC 2: KHI n != 0 LẶP
    NẾU !(n & 1) THÌ ind = i
    i++
    n = n >> 1
KẾT THÚC KHI
BƯỚC 3: TRẢ VỀ ind
KẾT THÚC

void perform_steps(int n)
BẮT ĐẦU
BƯỚC 1: left = find_leftmost_unsetbit(n)
BƯỚC 2: NẾU left == -1 THÌ IN "No Steps...", TRẢ VỀ
BƯỚC 3: step = 1
BƯỚC 4: KHI find_leftmost_unsetbit(n) != -1 LẶP
    NẾU step % 2 == 0 THÌ
        n++
        IN "Step n: Increase by 1"
    NGƯỢC LẠI
        m = find_leftmost_unsetbit(n)
        num = 2^m - 1
        n = n ^ num
        IN "Step N: Xor with Num"
    KẾT THÚC NẾU
    step++
KẾT THÚC KHI
KẾT THÚC

Chương trình C ví dụ

#include <stdio.h>
#include <math.h>

int find_leftmost_unsetbit(int n) {
    int ind = -1, i = 1;
    while (n) {
        if (!(n & 1)) ind = i;
        i++;
        n >>= 1;
    }
    return ind;
}

void perform_steps(int n) {
    int left = find_leftmost_unsetbit(n);
    if (left == -1) {
        printf("No Steps to be performed\n");
        return;
    }
    int step = 1;
    while (find_leftmost_unsetbit(n) != -1) {
        if (step % 2 == 0) {
            n += 1;
            printf("Step %d: Increase by 1\n", step);
        } else {
            int m = find_leftmost_unsetbit(n);
            int num = (int)(pow(2, m) - 1);
            n = n ^ num;
            printf("Step %d: Xor with %d\n", step, num);
        }
        step++;
    }
}

int main() {
    int n = 22;
    perform_steps(n);
    return 0;
}

Kết quả

Step 1: Xor with 15
Step 2: Increase by 1
Step 3: Xor with 7
Step 4: Increase by 1
Step 5: Xor with 1