有效地反转数字位的程序-yiteyi-C++库

给定一个非负整数N。任务是反转数字N的位，并打印反转后得到的数字的十进制等效值。笔记：不考虑前导0。 例如：

null

Input : 11
Output : 4
(11)₁₀ = (1011)₂
After inverting the bits, we get:
(0100)₂ = (4)₁₀.

Input : 20
Output : 11
(20)₁₀ = (10100)₂.
After inverting the bits, we get:
(01011)₂ = (11)₁₀.

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

类似的问题已经在本文中讨论过反转一个数字的实际位 . 本文讨论了一种使用位运算符的有效方法。下面是解决问题的逐步算法：

计算给定数字中的总位数。这可以通过计算：
```
X = log₂N
```
其中N是给定的数字，X是N的总位数。
下一步是生成一个设置了X位和所有位的数字。就是， 11111….X倍 。这可以通过计算：
```
Step-1: M = 1 << X
Step-2: M = M | (M-1)
```
其中M是设置了所有位的所需X位编号。
最后一步是计算M与N的位异或，这将是我们的答案。

以下是上述方法的实施情况：

C++

                         // C++ program to invert actual bits                       
                         // of a number.                       
                         #include <bits/stdc++.h>                       
                                   
                         using                                     namespace                                     std;                       
                                   
                         // Function to invert bits of a number                       
                         int                                     invertBits(                                     int                                     n)                       
                         {                       
                                                 // Calculate number of bits of N-1;                       
                                                 int                                     x = log2(n) ;                       
                                   
                                                 int                                     m = 1 << x;                       
                                   
                                                 m = m | m - 1;                       
                                   
                                                 n = n ^ m;                       
                                   
                                                 return                                     n;                       
                         }                       
                                   
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 20;                       
                                   
                                                 cout << invertBits(n);                       
                                   
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to invert                       
                         // actual bits of a number.                       
                         import                                     java.util.*;                       
                                   
                         class                                     GFG                       
                         {                       
                         // Function to invert                       
                         // bits of a number                       
                         static                                     int                                     invertBits(                                     int                                     n)                       
                         {                       
                                                 // Calculate number of bits of N-1;                       
                                                 int                                     x = (                                     int                                     )(Math.log(n) /                       
                                                 Math.log(                                     2                                     )) ;                       
                                   
                                                 int                                     m =                                     1                                     << x;                       
                                   
                                                 m = m | m -                                     1                                     ;                       
                                   
                                                 n = n ^ m;                       
                                   
                                                 return                                     n;                       
                         }                       
                                   
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     20                                     ;                       
                                   
                                                 System.out.print(invertBits(n));                       
                         }                       
                         }                       
                                   
                         // This code is contributed by Smitha                       

Python3

                         # Python3 program to invert actual                       
                         # bits of a number.                       
                         import                                     math                       
                                   
                         # Function to invert bits of a number                       
                         def                                     invertBits(n):                       
                                   
                                                 # Calculate number of bits of N-1                       
                                                 x                                     =                                     int                                     (math.log(n,                                     2                                     ))                       
                                   
                                                 m                                     =                                     1                                     << x                       
                                   
                                                 m                                     =                                     m | m                                     -                                     1                       
                                   
                                                 n                                     =                                     n ^ m                       
                                   
                                                 return                                     n                       
                                   
                         # Driver code                       
                         n                                     =                                     20                       
                                   
                         print                                     (invertBits(n))                       
                                   
                         # This code is contributed 29AjayKumar                       

C#

                         // C# program to invert                       
                         // actual bits of a number.                       
                         using                                     System;                       
                                   
                                   
                                   
                         public                                     class                                     GFG                       
                         {                       
                         // Function to invert                       
                         // bits of a number                       
                         static                                     int                                     invertBits(                                     int                                     n)                       
                         {                       
                                                 // Calculate number of bits of N-1;                       
                                                 int                                     x = (                                     int                                     )(Math.Log(n) /                       
                                                 Math.Log(2)) ;                       
                                   
                                                 int                                     m = 1 << x;                       
                                   
                                                 m = m | m - 1;                       
                                   
                                                 n = n ^ m;                       
                                   
                                                 return                                     n;                       
                         }                       
                                   
                         // Driver code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 int                                     n = 20;                       
                                   
                                                 Console.Write(invertBits(n));                       
                         }                       
                         }                       
                                   
                         // This code is contributed by Subhadeep                       

PHP

                         <?php                       
                         // PHP program to invert actual                       
                         // bits of a number.                       
                                   
                         // Function to invert bits                       
                         // of a number                       
                         function                                     invertBits(                                     $n                                     )                       
                         {                       
                                                 // Calculate number of                       
                                                 // bits of N-1;                       
                                                 $x                                     = log(                                     $n                                     , 2);                       
                                   
                                                 $m                                     = 1 <<                                     $x                                     ;                       
                                   
                                                 $m                                     =                                     $m                                     |                                     $m                                     - 1;                       
                                   
                                                 $n                                     =                                     $n                                     ^                                     $m                                     ;                       
                                   
                                                 return                                     $n                                     ;                       
                         }                       
                                   
                         // Driver code                       
                         $n                                     = 20;                       
                                   
                         echo                                     (invertBits(                                     $n                                     ));                       
                                   
                         // This code is contributed                       
                         // by mits                       
                         ?>                       

Javascript

                         <script>                       
                                   
                         // Javascript program to invert actual bits                       
                         // of a number.                       
                                   
                         // Function to invert bits of a number                       
                         function                                     invertBits(n)                       
                         {                       
                                                 // Calculate number of bits of N-1;                       
                                                 let x = parseInt(Math.log(n) / Math.log(2)) ;                       
                                   
                                                 let m = 1 << x;                       
                                   
                                                 m = m | m - 1;                       
                                   
                                                 n = n ^ m;                       
                                   
                                                 return                                     n;                       
                         }                       
                                   
                         // Driver code                       
                                                 let n = 20;                       
                                   
                                                 document.write(invertBits(n));                       
                                   
                         </script>                       

输出：

时间复杂性 ：O（对数） _2. n） 辅助空间 ：O（1）

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

THE END

技术文章