检查一个数字的位是否按递增顺序具有连续设置位的计数-yiteyi-C++库

给定一个整数n>0，任务是找出在整数计数的位模式中，连续1的值是否从左向右递增。

null

例如：

Input:19Output:YesExplanation: Bit-pattern of 19 = 10011,Counts of continuous 1's from left to right are 1, 2 which are in increasing order.Input  : 183Output : yesExplanation: Bit-pattern of 183 = 10110111,Counts of continuous 1's from left to right are 1, 2, 3 which are in increasing order.

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

A. 简单解决方案 是将给定数字的二进制表示形式存储到字符串中，然后从左向右遍历并计算连续1的个数。对于每次遇到0，请检查连续1的上一个计数到当前值的值，如果上一个计数的值大于当前计数的值，则返回False，否则在字符串结束时返回True。

C++

                         // C++ program to find if bit-pattern                       
                         // of a number has increasing value of                       
                         // continuous-1 or not.                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns true if n has increasing count of                       
                         // continuous-1 else false                       
                         bool                                     findContinuous1(                                     int                                     n)                       
                         {                       
                                                 const                                     int                                     bits = 8*                                     sizeof                                     (                                     int                                     );                       
           
                                                 // store the bit-pattern of n into                       
                                                 // bit bitset- bp                       
                                                 string bp = bitset <bits>(n).to_string();                       
           
                                                 // set prev_count = 0 and curr_count = 0.                       
                                                 int                                     prev_count = 0, curr_count = 0;                       
           
                                                 int                                     i = 0;                       
                                                 while                                     (i < bits)                       
                                                 {                       
                                                 if                                     (bp[i] ==                                     '1'                                     )                       
                                                 {                       
                                                 // increment current count of continuous-1                       
                                                 curr_count++;                       
                                                 i++;                       
                                                 }                       
           
                                                 // traverse all continuous-0                       
                                                 else                                     if                                     (bp[i-1] ==                                     '0'                                     )                       
                                                 {                       
                                                 i++;                       
                                                 curr_count = 0;                       
                                                 continue                                     ;                       
                                                 }                       
           
                                                 // check  prev_count and curr_count                       
                                                 // on encounter of first zero after                       
                                                 // continuous-1s                       
                                                 else                       
                                                 {                       
                                                 if                                     (curr_count < prev_count)                       
                                                 return                                     0;                       
                                                 i++;                       
                                                 prev_count=curr_count;                       
                                                 curr_count = 0;                       
                                                 }                       
                                                 }                       
           
                                                 // check for last sequence of continuous-1                       
                                                 if                                     (prev_count > curr_count && (curr_count != 0))                       
                                                 return                                     0;                       
           
                                                 return                                     1;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 179;                       
                                                 if                                     (findContinuous1(n))                       
                                                 cout <<                                     "Yes"                                     ;                       
                                                 else                       
                                                 cout <<                                     "No"                                     ;                       
           
                                                 return                                     0;                       
                         }                       

Python3

                         # Python3 program to find if bit-pattern                       
                         # of a number has increasing value of                       
                         # continuous-1 or not.                       
           
                         # Returns true if n has increasing count of                       
                         # continuous-1 else false                       
                         def                                     findContinuous1(n):                       
                                   
                                                 # store the bit-pattern of n into                       
                                                 # bit bitset- bp                       
                                                 bp                                     =                                     list                                     (                                     bin                                     (n))                       
                                   
                                                 bits                                     =                                     len                                     (bp)                       
                                   
                                                 # set prev_count = 0 and curr_count = 0.                       
                                                 prev_count                                     =                                     0                       
                                                 curr_count                                     =                                     0                       
                                   
                                                 i                                     =                                     0                       
                                                 while                                     (i < bits):                       
                                                 if                                     (bp[i]                                     =                                     =                                     '1'                                     ):                       
           
                                                 # increment current count of continuous-1                       
                                                 curr_count                                     +                                     =                                     1                       
                                                 i                                     +                                     =                                     1                       
                                   
                                                 # traverse all continuous-0                       
                                                 elif                                     (bp[i                                     -                                     1                                     ]                                     =                                     =                                     '0'                                     ):                       
                                                 i                                     +                                     =                                     1                       
                                                 curr_count                                     =                                     0                       
                                                 continue                       
                                   
                                                 # check prev_count and curr_count                       
                                                 # on encounter of first zero after                       
                                                 # continuous-1s                       
                                                 else                                     :                       
                                                 if                                     (curr_count < prev_count):                       
                                                 return                                     0                       
                                                 i                                     +                                     =                                     1                       
                                                 prev_count                                     =                                     curr_count                       
                                                 curr_count                                     =                                     0                       
                                   
                                                 # check for last sequence of continuous-1                       
                                                 if                                     (prev_count > curr_count                                     and                                     (curr_count !                                     =                                     0                                     )):                       
                                                 return                                     0                       
                                   
                                                 return                                     1                       
                                   
                         # Driver code                       
                         n                                     =                                     179                       
                         if                                     (findContinuous1(n)):                       
                                                 print                                     (                                     "Yes"                                     )                       
                         else                                     :                       
                                                 print                                     (                                     "No"                                     )                       
           
                         # This code is contributed by SHUBHAMSINGH10                       

Javascript

                         <script>                       
                         // JavaScript program to find if bit-pattern                       
                         // of a number has increasing value of                       
                         // continuous-1 or not.                       
                         function                                     dec2bin(dec) {                       
                                                 return                                     (dec >>> 0).toString(2);                       
                         }                       
                         // Returns true if n has increasing count of                       
                         // continuous-1 else false                       
                         function                                     findContinuous1(n){                       
                                                 // store the bit-pattern of n into                       
                                                 // bit bitset- bp                       
                                                 let bp = dec2bin(n)                       
                                                 let bits = bp.length                       
                                   
                                                 // set prev_count = 0 and curr_count = 0.                       
                                                 let prev_count = 0                       
                                                 let curr_count = 0                       
                                   
                                                 let i = 0                       
                                                 while                                     (i < bits){                       
                                                 if                                     (bp[i] ==                                     '1'                                     ){                       
                                                 // increment current count of continuous-1                       
                                                 curr_count += 1;                       
                                                 i += 1;                       
                                                 }                       
                                                 // traverse all continuous-0                       
                                                 else                                     if                                     (bp[i - 1] ==                                     '0'                                     ){                       
                                                 i += 1                       
                                                 curr_count = 0                       
                                                 continue                       
                                                 }                       
                                                 // check prev_count and curr_count                       
                                                 // on encounter of first zero after                       
                                                 // continuous-1s                       
                                                 else                                     {                       
                                                 if                                     (curr_count < prev_count)                       
                                                 return                                     0                       
                                                 i += 1                       
                                                 prev_count = curr_count                       
                                                 curr_count = 0                       
                                                 }                       
                                                 }                       
                                                 // check for last sequence of continuous-1                       
                                                 if                                     (prev_count > curr_count && (curr_count != 0))                       
                                                 return                                     0                       
                                   
                                                 return                                     1                       
                         }                       
                         // Driver code                       
                         n = 179                       
                         if                                     (findContinuous1(n))                       
                                                 document.write(                                     "Yes"                                     )                       
                         else                       
                                                 document.write(                                     "No"                                     )                       
           
                         </script>                       

输出：

Yes

一 有效解决方案 是使用十进制到二进制转换循环，将数字除以2，并将余数作为位。这个循环从右到左查找位。所以我们检查从右到左是否按降序排列。

下面是实现。

C++

                         // C++ program to check if counts of consecutive                       
                         // 1s are increasing order.                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns true if n has counts of consecutive                       
                         // 1's are increasing order.                       
                         bool                                     areSetBitsIncreasing(                                     int                                     n)                       
                         {                       
                                                 // Initialize previous count                       
                                                 int                                     prev_count = INT_MAX;                       
           
                                                 // We traverse bits from right to left                       
                                                 // and check if counts are decreasing                       
                                                 // order.                       
                                                 while                                     (n > 0)                       
                                                 {                       
                                                 // Ignore 0s until we reach a set bit.                       
                                                 while                                     (n > 0 && n % 2 == 0)                       
                                                 n = n/2;                       
           
                                                 // Count current set bits                       
                                                 int                                     curr_count = 1;                       
                                                 while                                     (n > 0 && n % 2 == 1)                       
                                                 {                       
                                                 n = n/2;                       
                                                 curr_count++;                       
                                                 }                       
           
                                                 // Compare current with previous and                       
                                                 // update previous.                       
                                                 if                                     (curr_count >= prev_count)                       
                                                 return                                     false                                     ;                       
                                                 prev_count = curr_count;                       
                                                 }                       
           
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 10;                       
                                                 if                                     (areSetBitsIncreasing(n))                       
                                                 cout <<                                     "Yes"                                     ;                       
                                                 else                       
                                                 cout <<                                     "No"                                     ;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to check if counts of                       
                         // consecutive 1s are increasing order.                       
                         import                                     java .io.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // Returns true if n has counts of                       
                                                 // consecutive 1's are increasing                       
                                                 // order.                       
                                                 static                                     boolean                                     areSetBitsIncreasing(                                     int                                     n)                       
                                                 {                       
                                   
                                                 // Initialize previous count                       
                                                 int                                     prev_count = Integer.MAX_VALUE;                       
                                   
                                                 // We traverse bits from right to                       
                                                 // left and check if counts are                       
                                                 // decreasing order.                       
                                                 while                                     (n >                                     0                                     )                       
                                                 {                       
                                   
                                                 // Ignore 0s until we reach                       
                                                 // a set bit.                       
                                                 while                                     (n >                                     0                                     && n %                                     2                                     ==                                     0                                     )                       
                                                 n = n/                                     2                                     ;                       
                                   
                                                 // Count current set bits                       
                                                 int                                     curr_count =                                     1                                     ;                       
                                                 while                                     (n >                                     0                                     && n %                                     2                                     ==                                     1                                     )                       
                                                 {                       
                                                 n = n/                                     2                                     ;                       
                                                 curr_count++;                       
                                                 }                       
                                   
                                                 // Compare current with previous                       
                                                 // and update previous.                       
                                                 if                                     (curr_count >= prev_count)                       
                                                 return                                     false                                     ;                       
                                                 prev_count = curr_count;                       
                                                 }                       
                                   
                                                 return                                     true                                     ;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 static                                     public                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     n =                                     10                                     ;                       
                                   
                                                 if                                     (areSetBitsIncreasing(n))                       
                                                 System.out.println(                                     "Yes"                                     );                       
                                                 else                       
                                                 System.out.println(                                     "No"                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

Python3

                         # Python3 program to check if counts of                       
                         # consecutive 1s are increasing order.                       
           
                         import                                     sys                       
           
                         # Returns true if n has counts of                       
                         # consecutive 1's are increasing order.                       
                         def                                     areSetBitsIncreasing(n):                       
           
                                                 # Initialize previous count                       
                                                 prev_count                                     =                                     sys.maxsize                       
           
                                                 # We traverse bits from right to                       
                                                 # left and check if counts are                       
                                                 # decreasing order.                       
                                                 while                                     (n >                                     0                                     ):                       
                                   
                                                 # Ignore 0s until we reach a                       
                                                 # set bit.                       
                                                 while                                     (n >                                     0                                     and                                     n                                     %                                     2                                     =                                     =                                     0                                     ):                       
                                                 n                                     =                                     int                                     (n                                     /                                     2                                     )                       
           
                                                 # Count current set bits                       
                                                 curr_count                                     =                                     1                       
                                                 while                                     (n >                                     0                                     and                                     n                                     %                                     2                                     =                                     =                                     1                                     ):                       
                                   
                                                 n                                     =                                     n                                     /                                     2                       
                                                 curr_count                                     +                                     =                                     1                       
                                   
                                                 # Compare current with previous                       
                                                 # and update previous.                       
                                                 if                                     (curr_count >                                     =                                     prev_count):                       
                                                 return                                     False                       
                                                 prev_count                                     =                                     curr_count                       
           
                                                 return                                     True                       
           
                         # Driver code                       
                         n                                     =                                     10                       
           
                         if                                     (areSetBitsIncreasing(n)):                       
                                                 print                                     (                                     "Yes"                                     )                       
                         else                                     :                       
                                                 print                                     (                                     "No"                                     )                       
                                   
                         # This code is contributed by Smitha                       

C#

                         // C# program to check if counts of                       
                         // consecutive 1s are increasing order.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Returns true if n has counts of                       
                                                 // consecutive 1's are increasing                       
                                                 // order.                       
                                                 static                                     bool                                     areSetBitsIncreasing(                                     int                                     n)                       
                                                 {                       
                                   
                                                 // Initialize previous count                       
                                                 int                                     prev_count =                                     int                                     .MaxValue;                       
                                   
                                                 // We traverse bits from right to                       
                                                 // left and check if counts are                       
                                                 // decreasing order.                       
                                                 while                                     (n > 0)                       
                                                 {                       
                                   
                                                 // Ignore 0s until we reach                       
                                                 // a set bit.                       
                                                 while                                     (n > 0 && n % 2 == 0)                       
                                                 n = n/2;                       
                                   
                                                 // Count current set bits                       
                                                 int                                     curr_count = 1;                       
                                                 while                                     (n > 0 && n % 2 == 1)                       
                                                 {                       
                                                 n = n/2;                       
                                                 curr_count++;                       
                                                 }                       
                                   
                                                 // Compare current with previous                       
                                                 // and update previous.                       
                                                 if                                     (curr_count >= prev_count)                       
                                                 return                                     false                                     ;                       
                                                 prev_count = curr_count;                       
                                                 }                       
                                   
                                                 return                                     true                                     ;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 static                                     public                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     n = 10;                       
                                   
                                                 if                                     (areSetBitsIncreasing(n))                       
                                                 Console.WriteLine(                                     "Yes"                                     );                       
                                                 else                       
                                                 Console.WriteLine(                                     "No"                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

PHP

                         <?php                       
                         // PHP program to check if                       
                         // counts of consecutive                       
                         // 1s are increasing order.                       
           
                         // Returns true if n has                       
                         // counts of consecutive                       
                         // 1's are increasing order.                       
                         function                                     areSetBitsIncreasing(                                     $n                                     )                       
                         {                       
                                                 // Initialize previous count                       
                                                 $prev_count                                     = PHP_INT_MAX;                       
           
                                                 // We traverse bits from right                       
                                                 // to left and check if counts                       
                                                 // are decreasing order.                       
                                                 while                                     (                                     $n                                     > 0)                       
                                                 {                       
                                                 // Ignore 0s until we                       
                                                 // reach a set bit.                       
                                                 while                                     (                                     $n                                     > 0 &&                                     $n                                     % 2 == 0)                       
                                                 $n                                     =                                     $n                                     / 2;                       
           
                                                 // Count current set bits                       
                                                 $curr_count                                     = 1;                       
                                                 while                                     (                                     $n                                     > 0                                     and                                     $n                                     % 2 == 1)                       
                                                 {                       
                                                 $n                                     =                                     $n                                     / 2;                       
                                                 $curr_count                                     ++;                       
                                                 }                       
           
                                                 // Compare current with previous                       
                                                 // and update previous.                       
                                                 if                                     (                                     $curr_count                                     >=                                     $prev_count                                     )                       
                                                 return                                     false;                       
                                                 $prev_count                                     =                                     $curr_count                                     ;                       
                                                 }                       
           
                                                 return                                     true;                       
                         }                       
           
                         // Driver code                       
                         $n                                     = 10;                       
                         if                                     (areSetBitsIncreasing(                                     $n                                     ))                       
                                                 echo                                     "Yes"                                     ;                       
                         else                       
                                                 echo                                     "No"                                     ;                       
           
                         // This code is contributed by anuj_67                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to check if counts of                       
                         // consecutive 1s are increasing order.                       
           
                         // Returns true if n has counts of                       
                         // consecutive 1's are increasing                       
                         // order.                       
                         function                                     areSetBitsIncreasing(n)                       
                         {                       
                                   
                                                 // Initialize previous count                       
                                                 var                                     prev_count = Number.MAX_VALUE;                       
           
                                                 // We traverse bits from right to                       
                                                 // left and check if counts are                       
                                                 // decreasing order.                       
                                                 while                                     (n > 0)                       
                                                 {                       
                                   
                                                 // Ignore 0s until we reach                       
                                                 // a set bit.                       
                                                 while                                     (n > 0 && n % 2 == 0)                       
                                                 n = parseInt(n / 2);                       
           
                                                 // Count current set bits                       
                                                 var                                     curr_count = 1;                       
                                                 while                                     (n > 0 && n % 2 == 1)                       
                                                 {                       
                                                 n = n / 2;                       
                                                 curr_count++;                       
                                                 }                       
           
                                                 // Compare current with previous                       
                                                 // and update previous.                       
                                                 if                                     (curr_count >= prev_count)                       
                                                 return                                     false                                     ;                       
                                   
                                                 prev_count = curr_count;                       
                                                 }                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver code                       
                         var                                     n = 10;                       
           
                         if                                     (areSetBitsIncreasing(n))                       
                                                 document.write(                                     "Yes"                                     );                       
                         else                       
                                                 document.write(                                     "No"                                     );                       
           
                         // This code is contributed by Rajput-Ji                       
           
                         </script>                       

输出：

No

时间复杂性： O（原木） _2. n）

辅助空间： O（1）

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

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

THE END

技术文章