在C程序中打印步骤以2 ^ X – 1的形式生成数字。
给定数字n，我们必须打印步骤以使用Xor操作将数字制成2^X-1的形式。
我们应该将数字与任何2^M-1进行XOR运算，其中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示例
#include <stdio.h>
#include <math.h>
//找到最左边的位
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;
//迭代直到数字为2^x-1-
while (find_leftmost_unsetbit(n) != -1) {
//如果步数是偶数则增加1-
if (step % 2 == 0) {
n += 1;
printf("Step %d: Increase by 1\n", step);
}
//如果步长是奇数，则用2^m-1进行xor-
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