使用按位AND将0转换为X的最大步骤-yiteyi-C++库

对于整数N，有从0到N-1的元素。某些元素可以转换为其他元素。每一次转换都需要一定的努力，对于每一次转换，这相当于1个单位。当且仅当A！=B和A&B=A（其中&是按位and运算符）。我们需要尽最大努力通过一系列转换从值为0的元素中获得值为X的元素。 例如：

null

输入：X=2 产出：1 获得2的唯一方法是直接将0转换为2（0和2的按位AND为0），因此需要一步。输入：X=3 产出：2 3可以通过两个步骤获得。首先，将0转换为1（0和1的按位AND为0）。然后，将1变换为3（1和3的按位AND为1）。

简单的解决方案是计算X中的设定位数。 说明： 首先，考虑一个单步从A到B的转换。A的所有设置位（等于1的位）都应设置在B中，否则A和B的按位AND将不等于A。如果有任何位设置在A中，但不在B中，则转换是不可能的。A的未设置位可以在B中设置或取消设置，这无关紧要。然后，我们可以通过在一个步骤中设置A中的所有未设置位来将A更改为B。因此，如果我们必须以最少的步骤将0转换为X，答案应该是1，因为0与任何数字的按位AND是0。但我们必须计算最大步长。因此，在每一步中，我们从右边开始设置每个位，一个设置的位一旦设置就不能被清除。 例子： 假设我们想要从0中获得13（二进制中为1101）。我们首先通过将0转换为1（二进制为0001）来设置右侧的第一位。接下来，我们将右边的第三位设置为5（二进制中的0101）。最后一步是设置第4位并获得13（1101）。

C++

                         // CPP code to find the maximum possible                       
                         // effort                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to get no of set bits in binary                       
                         // representation of positive integer n                       
                         unsigned                                     int                                     countSetBits(unsigned                                     int                                     n)                       
                         {                       
                                                 unsigned                                     int                                     count = 0;                       
                                                 while                                     (n) {                       
                                                 count += n & 1;                       
                                                 n >>= 1;                       
                                                 }                       
                                                 return                                     count;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     i = 3;                       
                                                 cout << countSetBits(i);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java code to find the maximum                       
                         // possible effort                       
           
                         class                                     GFG {                       
                                   
                         // Function to get no. of                       
                         // set bits in binary                       
                         // representation of                       
                         // positive integer n                       
                         static                                     int                                     countSetBits(                                     int                                     n)                       
                         {                       
                                                 int                                     count =                                     0                                     ;                       
                                                 while                                     (n !=                                     0                                     )                       
                                                 {                       
                                                 count += n &                                     1                                     ;                       
                                                 n >>=                                     1                                     ;                       
                                                 }                       
                                                 return                                     count;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     i =                                     3                                     ;                       
                                                 System.out.print(countSetBits(i));                       
                         }                       
                         }                       
           
                         // This code is contributed by Smitha.                       

Python3

                         # Python3 code to find the                       
                         # maximum possible effort                       
                                   
                         # Function to get no of                       
                         # set bits in binary                       
                         # representation of positive                       
                         # integer n                       
                         def                                     countSetBits(n) :                       
                                                 count                                     =                                     0                       
                                                 while                                     (n) :                       
                                                 count                                     +                                     =                                     n &                                     1                       
                                                 n >>                                     =                                     1                       
                                                 return                                     count                       
                                   
                         # Driver code                       
                         i                                     =                                     3                       
                         print                                     (countSetBits(i))                       
                                   
                         # This code is contributed by                       
                         # Manish Shaw(manishshaw1)                       

C#

                         // C# code to find the maximum                       
                         // possible effort                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                         // Function to get no. of                       
                         // set bits in binary                       
                         // representation of                       
                         // positive integer n                       
                         static                                     int                                     countSetBits(                                     int                                     n)                       
                         {                       
                                                 int                                     count = 0;                       
                                                 while                                     (n != 0)                       
                                                 {                       
                                                 count += n & 1;                       
                                                 n >>= 1;                       
                                                 }                       
                                                 return                                     count;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 int                                     i = 3;                       
                                                 Console.Write(countSetBits(i));                       
                         }                       
                         }                       
           
                         // This code is contributed by Smitha.                       

PHP

                         <?php                       
                         // PHP code to find the                       
                         // maximum possible effort                       
           
                         // Function to get no of                       
                         // set bits in binary                       
                         // representation of positive                       
                         // integer n                       
                         function                                     countSetBits(                                     $n                                     )                       
                         {                       
                                                 $count                                     = 0;                       
                                                 while                                     (                                     $n                                     )                       
                                                 {                       
                                                 $count                                     +=                                     $n                                     & 1;                       
                                                 $n                                     >>= 1;                       
                                                 }                       
                                                 return                                     $count                                     ;                       
                         }                       
           
                         // Driver code                       
                         $i                                     = 3;                       
                         echo                                     (countSetBits(                                     $i                                     ));                       
           
                         // This code is contributed by                       
                         // Manish Shaw(manishshaw1)                       
                         ?>                       

Javascript

                         <script>                       
                                   
                         // JavaScript code to find the maximum possible                       
                         // effort                       
           
                         // Function to get no of set bits in binary                       
                         // representation of positive integer n                       
                         function                                     countSetBits(n)                       
                         {                       
                                                 var                                     count = 0;                       
                                                 while                                     (n) {                       
                                                 count += n & 1;                       
                                                 n >>= 1;                       
                                                 }                       
                                                 return                                     count;                       
                         }                       
           
                         // Driver code                       
                         var                                     i = 3;                       
                         document.write( countSetBits(i));                       
           
                         </script>                       

输出：

时间复杂性： O（原木） ₁₀ N）

辅助空间： O（1）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章