在最高有效位之后切换所有位-yiteyi-C++库

给定一个数字，在最高有效位（包括最高有效位）之后切换该数字的所有位。

null

例如：

Input : 10 Output : 5Binary representation of 10 is 1010After toggling we get 0101Input : 5Output : 2

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们可以通过对1进行异或来切换位（注意1^0=1和1^1=0）。这个想法是采取一个数字 临时雇员 只设置了一个位。一个接一个的移动 临时雇员 然后用n对其进行异或运算，直到它跨过n的MSB（最高有效位）。

C++

                         // CPP program to toggle set  bits starting                       
                         // from MSB                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         void                                     toggle(                                     int                                     &n)                       
                         {                       
                                                 // temporary variable to                       
                                                 // use XOR with one of a n                       
                                                 int                                     temp = 1;                       
           
                                                 // Run loop until the only                       
                                                 // set bit in temp crosses                       
                                                 // MST of n.                       
                                                 while                                     (temp <= n)                       
                                                 {                       
                                                 // Toggle bit of n                       
                                                 // corresponding to                       
                                                 // current set bit in                       
                                                 // temp.                       
                                                 n = n ^ temp;                       
           
                                                 // Move set bit to next                       
                                                 // higher position.                       
                                                 temp = temp << 1;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 10;                       
                                                 toggle(n);                       
                                                 cout << n;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to toggle set                       
                         // bits starting from MSB                       
           
                         class                                     GFG {                       
                                   
                         static                                     int                                     toggle(                                     int                                     n) {                       
                                   
                                                 // temporary variable to                       
                                                 // use XOR with one of a n                       
                                                 int                                     temp =                                     1                                     ;                       
           
                                                 // Run loop until the only                       
                                                 // set bit in temp crosses                       
                                                 // MST of n.                       
                                                 while                                     (temp <= n) {                       
                                   
                                                 // Toggle bit of n                       
                                                 // corresponding to                       
                                                 // current set bit in                       
                                                 // temp.                       
                                                 n = n ^ temp;                       
           
                                                 // Move set bit to next                       
                                                 // higher position.                       
                                                 temp = temp <<                                     1                                     ;                       
                                                 }                       
                                                 return                                     n;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String arg[])                       
                         {                       
                                                 int                                     n =                                     10                                     ;                       
                                                 n = toggle(n);                       
                                                 System.out.print(n);                       
                         }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python program to toggle                       
                         # set  bits starting                       
                         # from MSB                       
           
                         def                                     toggle(n):                       
           
                                                 # temporary variable to                       
                                                 # use XOR with one of a n                       
                                                 temp                                     =                                     1                       
                                   
                                                 #Run loop until the only                       
                                                 #set bit in temp crosses                       
                                                 #MST of n.                       
                                                 while                                     (temp <                                     =                                     n):                       
                                   
                                                 # Toggle bit of n                       
                                                 # corresponding to                       
                                                 # current set bit in                       
                                                 # temp.                       
                                                 n                                     =                                     n ^ temp                       
                                   
                                                 # Move set bit to next                       
                                                 # higher position.                       
                                                 temp                                     =                                     temp <<                                     1                       
           
                                                 return                                     n                       
                                   
                         # Driver code                       
           
                         n                                     =                                     10                       
                         n                                     =                                     toggle(n)                       
                         print                                     (n)                       
           
                         # This code is contributed                       
                         # by Anant Agarwal.                       

C#

                         // C# program to toggle set                       
                         // bits starting from MSB                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                         // Function to toggle bits                       
                         // starting from MSB                       
                         static                                     int                                     toggle(                                     int                                     n) {                       
                                   
                                                 // temporary variable to                       
                                                 // use XOR with one of a n                       
                                                 int                                     temp = 1;                       
           
                                                 // Run loop until the only                       
                                                 // set bit in temp crosses                       
                                                 // MST of n.                       
                                                 while                                     (temp <= n) {                       
                                   
                                                 // Toggle bit of n                       
                                                 // corresponding to                       
                                                 // current set bit in                       
                                                 // temp.                       
                                                 n = n ^ temp;                       
           
                                                 // Move set bit to next                       
                                                 // higher position.                       
                                                 temp = temp << 1;                       
                                                 }                       
                                                 return                                     n;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 int                                     n = 10;                       
                                                 n = toggle(n);                       
                                                 Console.Write(n);                       
                         }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal.                       

PHP

                         <?php                       
                         // PHP program to toggle set                       
                         // bits starting from MSB                       
           
                         function                                     toggle( &                                     $n                                     )                       
                         {                       
                                                 // temporary variable to                       
                                                 // use XOR with one of a n                       
                                                 $temp                                     = 1;                       
           
                                                 // Run loop until the only                       
                                                 // set bit in temp crosses                       
                                                 // MST of n.                       
                                                 while                                     (                                     $temp                                     <=                                     $n                                     )                       
                                                 {                       
                                                 // Toggle bit of n                       
                                                 // corresponding to                       
                                                 // current set bit in                       
                                                 // temp.                       
                                                 $n                                     =                                     $n                                     ^                                     $temp                                     ;                       
           
                                                 // Move set bit to next                       
                                                 // higher position.                       
                                                 $temp                                     =                                     $temp                                     << 1;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         $n                                     = 10;                       
                         toggle(                                     $n                                     );                       
                         echo                                     $n                                     ;                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to toggle set                       
                         // bits starting from MSB                       
                         function                                     toggle(n)                       
                         {                       
                                   
                                                 // Temporary variable to                       
                                                 // use XOR with one of a n                       
                                                 let temp = 1;                       
           
                                                 // Run loop until the only                       
                                                 // set bit in temp crosses                       
                                                 // MST of n.                       
                                                 while                                     (temp <= n)                       
                                                 {                       
                                   
                                                 // Toggle bit of n                       
                                                 // corresponding to                       
                                                 // current set bit in                       
                                                 // temp.                       
                                                 n = n ^ temp;                       
           
                                                 // Move set bit to next                       
                                                 // higher position.                       
                                                 temp = temp << 1;                       
                                                 }                       
                                                 return                                     n;                       
                         }                       
           
                         // Driver code                       
                         let n = 10;                       
                         n = toggle(n);                       
           
                         document.write(n);                       
           
                         // This code is contributed by subham348                       
           
                         </script>                       

输出：

在假设数字存储在32位的情况下，上述解决方案可以优化为在O（1）时间内工作。

C++

                         // CPP program to toggle set  bits starting                       
                         // from MSB                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns a number which has all set bits                       
                         // starting from MSB of n                       
                         int                                     setAllBitsAfterMSB(                                     int                                     n)                       
                         {                       
                                                 // This makes sure two bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n>>1;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n>>2;                       
           
                                                 n |= n>>4;                       
                                                 n |= n>>8;                       
                                                 n |= n>>16;                       
                                                 return                                     n;                       
                         }                       
           
                         void                                     toggle(                                     int                                     &n)                       
                         {                       
                                                 n = n ^ setAllBitsAfterMSB(n);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 10;                       
                                                 toggle(n);                       
                                                 cout << n;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to toggle set bits                       
                         // starting from MSB                       
           
                         class                                     GFG {                       
                                   
                         // Returns a number which has all                       
                         // set bits starting from MSB of n                       
                         static                                     int                                     setAllBitsAfterMSB(                                     int                                     n) {                       
                                   
                                                 // This makes sure two bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >>                                     1                                     ;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >>                                     2                                     ;                       
           
                                                 n |= n >>                                     4                                     ;                       
                                                 n |= n >>                                     8                                     ;                       
                                                 n |= n >>                                     16                                     ;                       
                                                 return                                     n;                       
                         }                       
                         static                                     int                                     toggle(                                     int                                     n)                       
                         {                       
                                                 n = n ^ setAllBitsAfterMSB(n);                       
                                                 return                                     n;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String arg[])                       
                         {                       
                                                 int                                     n =                                     10                                     ;                       
                                                 n = toggle(n);                       
                                                 System.out.print(n);                       
                         }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python program to toggle set  bits starting                       
                         # from MSB                       
           
                         # Returns a number which has all set bits                       
                         # starting from MSB of n                       
                         def                                     setAllBitsAfterMSB(n):                       
                                   
                                                 # This makes sure two bits                       
                                                 # (From MSB and including MSB)                       
                                                 # are set                       
                                                 n |                                     =                                     n>>                                     1                       
                                   
                                                 # This makes sure 4 bits                       
                                                 # (From MSB and including MSB)                       
                                                 # are set                       
                                                 n |                                     =                                     n>>                                     2                       
                                   
                                                 n |                                     =                                     n>>                                     4                       
                                                 n |                                     =                                     n>>                                     8                       
                                                 n |                                     =                                     n>>                                     16                       
                                                 return                                     n                       
           
                         def                                     toggle(n):                       
           
                                                 n                                     =                                     n ^ setAllBitsAfterMSB(n)                       
                                                 return                                     n                       
                                   
                         #Driver code                       
           
                         n                                     =                                     10                       
                         n                                     =                                     toggle(n)                       
                         print                                     (n)                       
                         # This code is contributed by Anant Agarwal.                       

C#

                         // C# program to toggle set bits                       
                         // starting from MSB                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Returns a number which has all                       
                                                 // set bits starting from MSB of n                       
                                                 static                                     int                                     setAllBitsAfterMSB(                                     int                                     n)                       
                                                 {                       
                                   
                                                 // This makes sure two bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >> 1;                       
                                   
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >> 2;                       
                                   
                                                 n |= n >> 4;                       
                                                 n |= n >> 8;                       
                                                 n |= n >> 16;                       
                                                 return                                     n;                       
                                                 }                       
                                   
                                                 static                                     int                                     toggle(                                     int                                     n)                       
                                                 {                       
                                                 n = n ^ setAllBitsAfterMSB(n);                       
                                                 return                                     n;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 10;                       
                                                 n = toggle(n);                       
                                                 Console.WriteLine(n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007.                       

PHP

                         <?php                       
                         // PHP program to toggle set                       
                         // bits starting from MSB                       
           
                         // Returns a number which                       
                         // has all set bits starting                       
                         // from MSB of n                       
                         function                                     setAllBitsAfterMSB(                                     $n                                     )                       
                         {                       
                                                 // This makes sure two bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 $n                                     |=                                     $n                                     >> 1;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 $n                                     |=                                     $n                                     >> 2;                       
           
                                                 $n                                     |=                                     $n                                     >> 4;                       
                                                 $n                                     |=                                     $n                                     >> 8;                       
                                                 $n                                     |=                                     $n                                     >> 16;                       
                                                 return                                     $n                                     ;                       
                         }                       
                         function                                     toggle(&                                     $n                                     )                       
                         {                       
                                                 $n                                     =                                     $n                                     ^ setAllBitsAfterMSB(                                     $n                                     );                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 10;                       
                         toggle(                                     $n                                     );                       
                         echo                                     $n                                     ;                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to toggle set  bits starting                       
                         // from MSB                       
           
                         // Returns a number which has all set bits                       
                         // starting from MSB of n                       
                         function                                     setAllBitsAfterMSB(n)                       
                         {                       
                                                 // This makes sure two bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n>>1;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n>>2;                       
           
                                                 n |= n>>4;                       
                                                 n |= n>>8;                       
                                                 n |= n>>16;                       
                                                 return                                     n;                       
                         }                       
           
                         function                                     toggle(n)                       
                         {                       
                                                 n = n ^ setAllBitsAfterMSB(n);                       
                                                 return                                     n;                       
                         }                       
           
                         // Driver code                       
                                                 let n = 10;                       
                                                 document.write(toggle(n));                       
           
                         </script>                       

输出：

幸亏 德万舒阿加瓦尔 感谢你提出这种方法。

本文由 德万舒阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章