的形式打印制作数字的步骤
原文:
给定一个数字 n ，需要执行两个步骤。
- 奇数步，将数字与任意 2^m-1 异或，其中 m 由你选择。
- 偶数步，增加 1 号。
继续执行这些步骤，直到 n 变成 2^x-1 (其中 x 可以是任意整数)。任务是打印所有步骤。 例:
输入: 39 输出: 第 1 步:与 31 异或第 2 步:增加 1 第 3 步:与 7 异或第 4 步:增加 1 pick m = 5，n 转化为 39 ^ 31 = 56。 增加 n 1，将其值改为 n = 57。 pick m = 3，x 转化为 57 ^ 7 = 62。 将 x 增加 1，将其值更改为 63 = 2^6–1。 输入: 7 输出:不需要步骤。
接近:可以按照以下步骤解决上述问题:
- 在每一个奇数步，找到数字中最左边的未设置位(比如 1 索引中的位置 x)，并与 2^x-1.进行异或运算
- 在每一个偶数步，将数字增加 1。
- 如果在任何一步，该数字没有未设置的位，则返回。
以下是上述方法的实现:
c
// c program to implement
// the above approach
#include
using namespace std;
// function to find the leftmost
// unset bit in a number.
int find_leftmost_unsetbit(int n)
{
int ind = -1;
int i = 1;
while (n) {
if (!(n & 1))
ind = i;
i ;
n >>= 1;
}
return ind;
}
// function that perform
// the step
void perform_steps(int n)
{
// find the leftmost unset bit
int left = find_leftmost_unsetbit(n);
// if the number has no bit
// unset, it means it is in form 2^x -1
if (left == -1) {
cout << "no steps required";
return;
}
// count the steps
int step = 1;
// iterate till number is of form 2^x - 1
while (find_leftmost_unsetbit(n) != -1) {
// at even step increase by 1
if (step % 2 == 0) {
n = 1;
cout << "step" << step << ": increase by 1\n";
}
// odd step xor with any 2^m-1
else {
// find the leftmost unset bit
int m = find_leftmost_unsetbit(n);
// 2^m-1
int num = pow(2, m) - 1;
// perform the step
n = n ^ num;
cout << "step" << step
<< ": xor with " << num << endl;
}
// increase the steps
step = 1;
}
}
// driver code
int main()
{
int n = 39;
perform_steps(n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to implement
// the above approach
class gfg
{
// function to find the leftmost
// unset bit in a number.
static int find_leftmost_unsetbit(int n)
{
int ind = -1;
int i = 1;
while (n > 0)
{
if ((n % 2) != 1)
{
ind = i;
}
i ;
n >>= 1;
}
return ind;
}
// function that perform
// the step
static void perform_steps(int n)
{
// find the leftmost unset bit
int left = find_leftmost_unsetbit(n);
// if the number has no bit
// unset, it means it is in form 2^x -1
if (left == -1)
{
system.out.print("no steps required");
return;
}
// count the steps
int step = 1;
// iterate till number is of form 2^x - 1
while (find_leftmost_unsetbit(n) != -1)
{
// at even step increase by 1
if (step % 2 == 0)
{
n = 1;
system.out.println("step" step ": increase by 1");
}
// odd step xor with any 2^m-1
else
{
// find the leftmost unset bit
int m = find_leftmost_unsetbit(n);
// 2^m-1
int num = (int) (math.pow(2, m) - 1);
// perform the step
n = n ^ num;
system.out.println("step" step
": xor with " num);
}
// increase the steps
step = 1;
}
}
// driver code
public static void main(string[] args)
{
int n = 39;
perform_steps(n);
}
}
// this code contributed by rajput-ji
python 3
# python3 program to implement
# the above approach
# function to find the leftmost
# unset bit in a number.
def find_leftmost_unsetbit(n):
ind = -1;
i = 1;
while (n):
if ((n % 2) != 1):
ind = i;
i = 1;
n >>= 1;
return ind;
# function that perform
# the step
def perform_steps(n):
# find the leftmost unset bit
left = find_leftmost_unsetbit(n);
# if the number has no bit
# unset, it means it is in form 2^x -1
if (left == -1):
print("no steps required");
return;
# count the steps
step = 1;
# iterate till number is of form 2^x - 1
while (find_leftmost_unsetbit(n) != -1):
# at even step increase by 1
if (step % 2 == 0):
n = 1;
print("step" , step ,
": increase by 1\n");
# odd step xor with any 2^m-1
else:
# find the leftmost unset bit
m = find_leftmost_unsetbit(n);
# 2^m-1
num = (2**m) - 1;
# perform the step
n = n ^ num;
print("step" , step,
": xor with" , num );
# increase the steps
step = 1;
# driver code
n = 39;
perform_steps(n);
# this code contributed by princiraj1992
c
// c# program to implement
// the above approach
using system;
class gfg
{
// function to find the leftmost
// unset bit in a number.
static int find_leftmost_unsetbit(int n)
{
int ind = -1;
int i = 1;
while (n > 0)
{
if ((n % 2) != 1)
{
ind = i;
}
i ;
n >>= 1;
}
return ind;
}
// function that perform
// the step
static void perform_steps(int n)
{
// find the leftmost unset bit
int left = find_leftmost_unsetbit(n);
// if the number has no bit
// unset, it means it is in form 2^x -1
if (left == -1)
{
console.write("no steps required");
return;
}
// count the steps
int step = 1;
// iterate till number is of form 2^x - 1
while (find_leftmost_unsetbit(n) != -1)
{
// at even step increase by 1
if (step % 2 == 0)
{
n = 1;
console.writeline("step" step ": increase by 1");
}
// odd step xor with any 2^m-1
else
{
// find the leftmost unset bit
int m = find_leftmost_unsetbit(n);
// 2^m-1
int num = (int) (math.pow(2, m) - 1);
// perform the step
n = n ^ num;
console.writeline("step" step
": xor with " num);
}
// increase the steps
step = 1;
}
}
// driver code
static public void main ()
{
int n = 39;
perform_steps(n);
}
}
// this code contributed by ajit.
服务器端编程语言（professional hypertext preprocessor 的缩写）
>= 1;
}
return $ind;
}
// function that perform
// the step
function perform_steps($n)
{
// find the leftmost unset bit
$left = find_leftmost_unsetbit($n);
// if the number has no bit
// unset, it means it is in form 2^x -1
if ($left == -1)
{
echo "no steps required";
return;
}
// count the steps
$step = 1;
// iterate till number is of form 2^x - 1
while (find_leftmost_unsetbit($n) != -1)
{
// at even step increase by 1
if ($step % 2 == 0)
{
$n = 1;
echo "step",$step, ": increase by 1\n";
}
// odd step xor with any 2^m-1
else
{
// find the leftmost unset bit
$m = find_leftmost_unsetbit($n);
// 2^m-1
$num = pow(2, $m) - 1;
// perform the step
$n = $n ^ $num;
echo "step",$step ,": xor with ", $num ,"\n";
}
// increase the steps
$step = 1;
}
}
// driver code
$n = 39;
perform_steps($n);
// this code is contributed by ryuga
?>
java 描述语言
output:
step1: xor with 31
step2: increase by 1
step3: xor with 7
step4: increase by 1
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
