检查位在给定范围内是否处于交替模式-yiteyi-C++库

给定一个非负数 N 还有两个价值观 L 和 R .问题是要检查 N 在范围内的二进制表示中有一个替代模式 L 到 R 这里的交替模式意味着设置位和未设置位以交替顺序出现。位从右向左编号，即最低有效位被认为位于第一位置。 限制条件： 1<=l<=r<=二进制表示中的位数 N . 例如：

null

Input : n = 18, l = 1, r = 3Output : Yes(18)₁₀ = (10010)₂The bits in the range 1 to 3 in thebinary representation of 18 are inalternate order.Input : n = 22, l = 2, r = 4Output : No(22)₁₀ = (10110)₂The bits in the range 2 to 4 in thebinary representation of 22 are not inalternate order.

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

算法：

bitsAreInAltPatrnInGivenTRange(n, l, r)        // Shift bits of given number n by     // (l-1).    num = n >> (l - 1)        // Find first bit of range    prev = num & 1    // Traverse through remaining    // bits. For every bit, check if    // current bit is same as previous    // or not.    num = num >> 1        for i = 1 to (r - l)        curr = num & 1                if curr == prev then            return false                prev = curr        num = num >> 1        return true;

C++

                         // C++ implementation to check whether bits are in                       
                         // alternate pattern in the given range                       
                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         // function to check whether bits are in                       
                         // alternate pattern in the given range                       
                         bool                                     bitsAreInAltPatrnInGivenTRange(unsigned                                     int                                     n,                       
                                                 unsigned                                     int                                     l,                       
                                                 unsigned                                     int                                     r)                       
                         {                       
                                                 unsigned                                     int                                     num, prev, curr;                       
           
                                                 // right shift n by (l - 1) bits                       
                                                 num = n >> (l - 1);                       
           
                                                 // get the bit at the last position in 'num'                       
                                                 prev = num & 1;                       
           
                                                 // right shift 'num' by 1                       
                                                 num = num >> 1;                       
           
                                                 // loop until there are bits in the given range                       
                                                 for                                     (                                     int                                     i = 1; i <= (r - l); i++) {                       
           
                                                 // get the bit at the last position in 'num'                       
                                                 curr = num & 1;                       
           
                                                 // if true, then bits are not in alternate                       
                                                 // pattern                       
                                                 if                                     (curr == prev)                       
                                                 return                                     false                                     ;                       
           
                                                 // update 'prev'                       
                                                 prev = curr;                       
           
                                                 // right shift 'num' by 1                       
                                                 num = num >> 1;                       
                                                 }                       
           
                                                 // bits are in alternate pattern in the                       
                                                 // given range                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver program to test above                       
                         int                                     main()                       
                         {                       
                                                 unsigned                                     int                                     n = 18;                       
                                                 unsigned                                     int                                     l = 1, r = 3;                       
           
                                                 if                                     (bitsAreInAltPatrnInGivenTRange(n, l, r))                       
                                                 cout <<                                     "Yes"                                     ;                       
                                                 else                       
                                                 cout <<                                     "No"                                     ;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation to check                       
                         // whether bits are in alternate                       
                         // pattern in the given range                       
                         class                                     GFG                       
                         {                       
                                   
                         // function to check whether                       
                         // bits are in alternate                       
                         // pattern in the given range                       
                         static                                     boolean                                     bitsAreInAltPatrnInGivenTRange(                                     int                                     n,                       
                                                 int                                     l,                                     int                                     r)                       
                         {                       
                                                 int                                     num, prev, curr;                       
           
                                                 // right shift n by (l - 1) bits                       
                                                 num = n >> (l -                                     1                                     );                       
           
                                                 // get the bit at the                       
                                                 // last position in 'num'                       
                                                 prev = num &                                     1                                     ;                       
           
                                                 // right shift 'num' by 1                       
                                                 num = num >>                                     1                                     ;                       
           
                                                 // loop until there are                       
                                                 // bits in the given range                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= (r - l); i++)                       
                                                 {                       
           
                                                 // get the bit at the                       
                                                 // last position in 'num'                       
                                                 curr = num &                                     1                                     ;                       
           
                                                 // if true, then bits are                       
                                                 // not in alternate pattern                       
                                                 if                                     (curr == prev)                       
                                                 return                                     false                                     ;                       
           
                                                 // update 'prev'                       
                                                 prev = curr;                       
           
                                                 // right shift 'num' by 1                       
                                                 num = num >>                                     1                                     ;                       
                                                 }                       
           
                                                 // bits are in alternate                       
                                                 // pattern in the given range                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     18                                     ;                       
                                                 int                                     l =                                     1                                     , r =                                     3                                     ;                       
           
                                                 if                                     (bitsAreInAltPatrnInGivenTRange(n, l, r))                       
                                                 System.out.println(                                     "Yes"                                     );                       
                                                 else                       
                                                 System.out.println(                                     "No"                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed by mits                       

Python3

                         # Python3 implementation to check                       
                         # whether bits are in alternate                       
                         # pattern in the given range                       
           
                         # function to check whether                       
                         # bits are in alternate                       
                         # pattern in the given range                       
                         def                                     bitsAreInAltPatrnInGivenTRange(n, l, r):                       
           
                                                 # right shift n by (l - 1) bits                       
                                                 num                                     =                                     n >> (l                                     -                                     1                                     );                       
           
                                                 # get the bit at the                       
                                                 # last position in 'num'                       
                                                 prev                                     =                                     num &                                     1                                     ;                       
           
                                                 # right shift 'num' by 1                       
                                                 num                                     =                                     num >>                                     1                                     ;                       
           
                                                 # loop until there are                       
                                                 # bits in the given range                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,(r                                     -                                     l)):                       
           
                                                 # get the bit at the                       
                                                 # last position in 'num'                       
                                                 curr                                     =                                     num &                                     1                                     ;                       
           
                                                 # if true, then bits are                       
                                                 # not in alternate pattern                       
                                                 if                                     (curr                                     =                                     =                                     prev):                       
                                                 return                                     False                                     ;                       
           
                                                 # update 'prev'                       
                                                 prev                                     =                                     curr;                       
           
                                                 # right shift 'num' by 1                       
                                                 num                                     =                                     num >>                                     1                                     ;                       
           
                                                 # bits are in alternate                       
                                                 # pattern in the given range                       
                                                 return                                     True                                     ;                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                                 n                                     =                                     18                                     ;                       
                                                 l                                     =                                     1                                     ;                       
                                                 r                                     =                                     3                                     ;                       
           
                                                 if                                     (bitsAreInAltPatrnInGivenTRange(n, l, r)):                       
                                                 print                                     (                                     "Yes"                                     );                       
                                                 else                                     :                       
                                                 print                                     (                                     "No"                                     );                       
           
                         # This Code is contributed by mits                       

C#

                         // C# implementation to check                       
                         // whether bits are in alternate                       
                         // pattern in the given range                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // function to check whether                       
                         // bits are in alternate                       
                         // pattern in the given range                       
                         static                                     bool                                     bitsAreInAltPatrnInGivenTRange(                                     int                                     n,                       
                                                 int                                     l,                                     int                                     r)                       
                         {                       
                                                 int                                     num, prev, curr;                       
           
                                                 // right shift n by (l - 1) bits                       
                                                 num = n >> (l - 1);                       
           
                                                 // get the bit at the                       
                                                 // last position in 'num'                       
                                                 prev = num & 1;                       
           
                                                 // right shift 'num' by 1                       
                                                 num = num >> 1;                       
           
                                                 // loop until there are                       
                                                 // bits in the given range                       
                                                 for                                     (                                     int                                     i = 1; i <= (r - l); i++)                       
                                                 {                       
           
                                                 // get the bit at the                       
                                                 // last position in 'num'                       
                                                 curr = num & 1;                       
           
                                                 // if true, then bits are                       
                                                 // not in alternate pattern                       
                                                 if                                     (curr == prev)                       
                                                 return                                     false                                     ;                       
           
                                                 // update 'prev'                       
                                                 prev = curr;                       
           
                                                 // right shift 'num' by 1                       
                                                 num = num >> 1;                       
                                                 }                       
           
                                                 // bits are in alternate                       
                                                 // pattern in the given range                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver Code                       
                         static                                     void                                     Main()                       
                         {                       
                                                 int                                     n = 18;                       
                                                 int                                     l = 1, r = 3;                       
           
                                                 if                                     (bitsAreInAltPatrnInGivenTRange(n, l, r))                       
                                                 Console.WriteLine(                                     "Yes"                                     );                       
                                                 else                       
                                                 Console.WriteLine(                                     "No"                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed by mits                       

PHP

                         <?php                       
                         // PHP implementation to check                       
                         // whether bits are in alternate                       
                         // pattern in the given range                       
           
                         // function to check whether                       
                         // bits are in alternate                       
                         // pattern in the given range                       
                         function                                     bitsAreInAltPatrnInGivenTRange(                                     $n                                     ,                                     $l                                     ,                                     $r                                     )                       
                         {                       
           
                                                 // right shift n by (l - 1) bits                       
                                                 $num                                     =                                     $n                                     >> (                                     $l                                     - 1);                       
           
                                                 // get the bit at the                       
                                                 // last position in 'num'                       
                                                 $prev                                     =                                     $num                                     & 1;                       
           
                                                 // right shift 'num' by 1                       
                                                 $num                                     =                                     $num                                     >> 1;                       
           
                                                 // loop until there are                       
                                                 // bits in the given range                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <= (                                     $r                                     -                                     $l                                     );                                     $i                                     ++)                       
                                                 {                       
           
                                                 // get the bit at the                       
                                                 // last position in 'num'                       
                                                 $curr                                     =                                     $num                                     & 1;                       
           
                                                 // if true, then bits are                       
                                                 // not in alternate pattern                       
                                                 if                                     (                                     $curr                                     ==                                     $prev                                     )                       
                                                 return                                     false;                       
           
                                                 // update 'prev'                       
                                                 $prev                                     =                                     $curr                                     ;                       
           
                                                 // right shift 'num' by 1                       
                                                 $num                                     =                                     $num                                     >> 1;                       
                                                 }                       
           
                                                 // bits are in alternate                       
                                                 // pattern in the given range                       
                                                 return                                     true;                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 18;                       
                         $l                                     = 1;                       
                         $r                                     = 3;                       
           
                         if                                     (bitsAreInAltPatrnInGivenTRange(                                     $n                                     ,                                     $l                                     ,                                     $r                                     ))                       
                                                 echo                                     "Yes"                                     ;                       
                         else                       
                                                 echo                                     "No"                                     ;                       
           
                         // This Code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript implementation to check whether bits are in                       
                         // alternate pattern in the given range                       
           
                         // function to check whether bits are in                       
                         // alternate pattern in the given range                       
                         function                                     bitsAreInAltPatrnInGivenTRange(n, l, r)                       
                         {                       
                                                 var                                     num, prev, curr;                       
           
                                                 // right shift n by (l - 1) bits                       
                                                 num = n >> (l - 1);                       
           
                                                 // get the bit at the last position in 'num'                       
                                                 prev = num & 1;                       
           
                                                 // right shift 'num' by 1                       
                                                 num = num >> 1;                       
           
                                                 // loop until there are bits in the given range                       
                                                 for                                     (                                     var                                     i = 1; i <= (r - l); i++) {                       
           
                                                 // get the bit at the last position in 'num'                       
                                                 curr = num & 1;                       
           
                                                 // if true, then bits are not in alternate                       
                                                 // pattern                       
                                                 if                                     (curr == prev)                       
                                                 return                                     false                                     ;                       
           
                                                 // update 'prev'                       
                                                 prev = curr;                       
           
                                                 // right shift 'num' by 1                       
                                                 num = num >> 1;                       
                                                 }                       
           
                                                 // bits are in alternate pattern in the                       
                                                 // given range                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver program to test above                       
                         var                                     n = 18;                       
                         var                                     l = 1, r = 3;                       
                         if                                     (bitsAreInAltPatrnInGivenTRange(n, l, r))                       
                                                 document.write(                                     "Yes"                                     );                       
                         else                       
                                                 document.write(                                     "No"                                     );                       
           
                         // This code is contributed by rrrtnx.                       
                         </script>                       

输出：

Yes

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

THE END

技术文章