给定n，求出严格不超过n的最大数，其二进制表示由m个连续的1，然后是m-1个连续的零和其他任何东西组成 例如：
null
Input : n = 7 Output : 6 Explanation: 6's binary representation is 110,and 7's is 111, so 6 consists of 2 consecutive 1's and then 1 consecutive 0.Input : 130Output : 120 Explanation: 28 and 120 are the only numbers <=120,28 is 11100 consists of 3 consecutive 1's and then 2 consecutive 0's. 120 is 1111000 consists of 4 consecutive 1's and then 3 consecutive 0's. So 120is the greatest of number<=120 which meets thegiven condition.
A. 幼稚的方法 将从1遍历到N，检查由m个连续1和m-1个连续0组成的每个二进制表示，并存储满足给定条件的最大二进制表示。 一 有效的方法 就是观察数字的模式， [ 1(1), 6(110), 28(11100), 120(1111000), 496(111110000), ….] 为了得到满足条件的数的公式，我们以120为例- 120表示为1111000，其中m=4 1，m=3 0。将1111000转换为十进制，我们得到： 2^3+2^4+2^5+2^6可以表示为（2^m-1+2^m+2^m+1+…2^m+2，2^2*m） 2^3*（1+2+2^2+2^3），可以表示为（2^（m-1）*（1+2+2^2+2^3+…2^（m-1）） 2^3*（2^4-1）可以表示为 [2^（m-1）*（2^m-1）]。 所以所有满足给定条件的数字都可以表示为
[2^（m-1）*（2^m-1）]
我们可以迭代，直到数字不超过N，然后打印所有可能元素中的最大元素。仔细观察就会发现 m=33将超过10^18分 ，所以我们计算单位时间内的数字为 日志（32） 接近常数，这是计算 战俘 . 因此，总体复杂性将为O（1）。
C++
// CPP program to find largest number // smaller than equal to n with m set // bits then m-1 0 bits. #include <bits/stdc++.h> using namespace std; // Returns largest number with m set // bits then m-1 0 bits. long long answer( long long n) { // Start with 2 bits. long m = 2; // initial answer is 1 // which meets the given condition long long ans = 1; long long r = 1; // check for all numbers while (r < n) { // compute the number r = ( int )( pow (2, m) - 1) * ( pow (2, m - 1)); // if less then N if (r < n) ans = r; // increment m to get the next number m++; } return ans; } // driver code to check the above condition int main() { long long n = 7; cout << answer(n); return 0; } |
JAVA
// java program to find largest number // smaller than equal to n with m set // bits then m-1 0 bits. public class GFG { // Returns largest number with // m set bits then m-1 0 bits. static long answer( long n) { // Start with 2 bits. long m = 2 ; // initial answer is 1 which // meets the given condition long ans = 1 ; long r = 1 ; // check for all numbers while (r < n) { // compute the number r = (( long )Math.pow( 2 , m) - 1 ) * (( long )Math.pow( 2 , m - 1 )); // if less then N if (r < n) ans = r; // increment m to get // the next number m++; } return ans; } // Driver code public static void main(String args[]) { long n = 7 ; System.out.println(answer(n)); } } // This code is contributed by Sam007 |
Python3
# Python3 program to find # largest number smaller # than equal to n with m # set bits then m-1 0 bits. import math # Returns largest number # with m set bits then # m-1 0 bits. def answer(n): # Start with 2 bits. m = 2 ; # initial answer is # 1 which meets the # given condition ans = 1 ; r = 1 ; # check for all numbers while r < n: # compute the number r = ( int )(( pow ( 2 , m) - 1 ) * ( pow ( 2 , m - 1 ))); # if less then N if r < n: ans = r; # increment m to get # the next number m = m + 1 ; return ans; # Driver Code print (answer( 7 )); # This code is contributed by mits. |
C#
// C# program to find largest number // smaller than equal to n with m set // bits then m-1 0 bits. using System; class GFG { // Returns largest number with // m set bits then m-1 0 bits. static long answer( long n) { // Start with 2 bits. long m = 2; // initial answer is 1 which // meets the given condition long ans = 1; long r = 1; // check for all numbers while (r < n) { // compute the number r = (( long )Math.Pow(2, m) - 1) * (( long )Math.Pow(2, m - 1)); // if less then N if (r < n) ans = r; // increment m to get // the next number m++; } return ans; } // Driver Code static public void Main () { long n = 7; Console.WriteLine(answer(n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find largest number // smaller than equal to n with m set // bits then m-1 0 bits. // Returns largest number with m set // bits then m-1 0 bits. function answer( $n ) { // Start with 2 bits. $m = 2; // initial answer is 1 // which meets the // given condition $ans = 1; $r = 1; // check for all numbers while ( $r < $n ) { // compute the number $r = (pow(2, $m ) - 1) * (pow(2, $m - 1)); // if less then N if ( $r < $n ) $ans = $r ; // increment m to get // the next number $m ++; } return $ans ; } // Driver Code $n = 7; echo answer( $n ); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript program to find largest number // smaller than equal to n with m set // bits then m-1 0 bits. // Returns largest number with // m set bits then m-1 0 bits. function answer(n) { // Start with 2 bits. let m = 2; // initial answer is 1 which // meets the given condition let ans = 1; let r = 1; // check for all numbers while (r < n) { // compute the number r = (Math.pow(2, m) - 1) * (Math.pow(2, m - 1)); // if less then N if (r < n) ans = r; // increment m to get // the next number m++; } return ans; } // Driver code let n = 7; document.write(answer(n)); </script> |
输出：
6
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
