给定一个数字 n，我们必须使用异或运算来打印将数字制成 2^x-1 形式的步骤。
我们应该进行异或任意 2^m-1 的数字，其中 m 由您选择，在奇数步长。 在偶数步长，将数字增加 1 继续执行该步骤，直到n变为2^x-1，并打印所有步骤
示例input: 22output: step 1 : xor with 15 step 2: increase by 1 step 3 : xor with 7 step 4: increase by 1 step 5 : xor with 1input:7output: no steps to be performed
算法int find_leftmost_unsetbit(int n)startstep 1 : declare and assign ind = -1, i = 1step 2 : loop while n if !(n & 1) then, assign ind with i end if increment i by 1 left shift n by 1end whilestep 3 : return indstopvoid perform_steps(int n)startstep 1 : declare and assign left = find_leftmost_unsetbit(n)step 2 : if left == -1 then, print "no steps to be performed" returnend ifstep 3 : declare and assign step = 1step 4 : loop while find_leftmost_unsetbit(n) != -1 if step % 2 == 0 then, increment n by 1 print "step n : increase by 1
" 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 1end loopstop
示例#include <stdio.h>#include <math.h>//to find the leftmost bitint 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){ // find the leftmost unset bit int left = find_leftmost_unsetbit(n); //if there is no bit if (left == -1) { printf("no steps to be performed
"); return; } // to count the number of steps int step = 1; // iterate till number is in form of 2^x - 1 while (find_leftmost_unsetbit(n) != -1) { // if the step is even then increase by 1 if (step % 2 == 0) { n += 1; printf("step %d: increase by 1
", step); } // if the step is odd then xor with 2^m-1 else { // finding the leftmost unset bit int m = find_leftmost_unsetbit(n); int num = (int)(pow(2, m) - 1); n = n ^ num; printf("step %d : xor with %d
", step, num); } // to increase the steps step += 1; }}int main(){ int n = 22; perform_steps(n); return 0;}
输出如果我们运行上面的程序，那么它将生成以下输出 -
step 1 : xor with 15step 2 : increase by 1step 3 : xor with 7step 4 : increase by 1step 5 : xor with 1
以上就是打印在c程序中生成形如2^x - 1的数字的步骤的详细内容。