การพิมพ์ขั้นตอนเพื่อทำให้เลขอยู่ในรูป 2^X - 1 ในโปรแกรม C

ได้รับตัวเลข n ให้พิมพ์ขั้นตอนการทำให้ตัวเลขอยู่ในรูป 2^X-1 โดยใช้การดำเนินการ XOR

• ขั้นคี่: XOR เลขกับ 2^M-1 โดย M เลือกเอง
• ขั้นคู่: เพิ่มเลขขึ้น 1

ทำซ้ำจนกว่า n จะกลายเป็น 2^X-1 และพิมพ์ทุกขั้นตอน

ตัวอย่าง

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

อัลกอริทึม

int find_leftmost_unsetbit(int n)
START
STEP 1: DECLARE AND ASSIGN ind = -1, i = 1
STEP 2: LOOP WHILE n
          IF !(n & 1) THEN
            ASSIGN ind WITH i
          END IF
          INCREMENT i BY 1
          LEFT SHIFT n BY 1
        END WHILE
STEP 3: RETURN ind
STOP

void perform_steps(int n)
START
STEP 1: DECLARE AND ASSIGN left = find_leftmost_unsetbit(n)
STEP 2: IF left == -1 THEN
          PRINT "No Steps to be performed"
          RETURN
        END IF
STEP 3: DECLARE AND ASSIGN step = 1
STEP 4: LOOP WHILE find_leftmost_unsetbit(n) != -1
          IF step % 2 == 0 THEN
            INCREMENT n BY 1
            PRINT "Step n : Increase by 1\n"
          ELSE
            DECLARE AND ASSIGN m = find_leftmost_unsetbit(n)
            AND SET num = (pow(2, m) - 1)
            SET n = n ^ num
            PRINT "Step N : Xor with Num"
          END IF
          INCREMENT step BY 1
        END LOOP
STOP

ตัวอย่างโค้ด C

#include 
#include 
// หาบิต 0 ที่อยู่ซ้ายสุด
int find_leftmost_unsetbit(int n){
    int ind = -1;
    int 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 += 1;
    }
}
int main(){
    int n = 22;
    perform_steps(n);
    return 0;
}

ผลลัพธ์

การรันโปรแกรมจะได้ผลลัพธ์ดังนี้:

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