打印所有前缀中1大于0的N位二进制数-yiteyi-C++库

给定一个正整数n，打印所有n位二进制数，对于该数字的任何前缀，其1大于0。

null

例如：

Input : n = 2Output : 11 10Input : n = 4Output : 1111 1110 1101 1100 1011 1010

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 易于理解的 但不是有效的解决方案是生成所有N位二进制数并打印满足条件的数字。这个解决方案的时间复杂度是指数的。

一 有效解决方案 只生成满足给定条件的N位数字。我们使用递归。在递归过程中的每一点上，我们将0和1附加到部分形成的数字上，并用少一个数字进行递归。

C++

                         // C++ program to print all N-bit binary                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         /* function to generate n  digit numbers*/                       
                         void                                     printRec(string number,                                     int                                     extraOnes,                       
                                                 int                                     remainingPlaces)                       
                         {                       
                                                 /* if number generated */                       
                                                 if                                     (0 == remainingPlaces) {                       
                                                 cout << number <<                                     " "                                     ;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 /* Append 1 at the current number and reduce                       
                                                 the remaining places by one */                       
                                                 printRec(number +                                     "1"                                     , extraOnes + 1,                       
                                                 remainingPlaces - 1);                       
           
                                                 /* If more ones than zeros, append 0 to the                       
                                                 current number and reduce the remaining                       
                                                 places by one*/                       
                                                 if                                     (0 < extraOnes)                       
                                                 printRec(number +                                     "0"                                     , extraOnes - 1,                       
                                                 remainingPlaces - 1);                       
                         }                       
           
                         void                                     printNums(                                     int                                     n)                       
                         {                       
                                                 string str =                                     ""                                     ;                       
                                                 printRec(str, 0, n);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 4;                       
                                   
                                                 // Function call                       
                                                 printNums(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print all N-bit binary                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                                 // function to generate n digit numbers                       
                                                 static                                     void                                     printRec(String number,                       
                                                 int                                     extraOnes,                       
                                                 int                                     remainingPlaces)                       
                                                 {                       
                                                 // if number generated                       
                                                 if                                     (                                     0                                     == remainingPlaces) {                       
                                                 System.out.print(number +                                     " "                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Append 1 at the current number and                       
                                                 // reduce the remaining places by one                       
                                                 printRec(number +                                     "1"                                     , extraOnes +                                     1                                     ,                       
                                                 remainingPlaces -                                     1                                     );                       
           
                                                 // If more ones than zeros, append 0 to the                       
                                                 // current number and reduce the remaining                       
                                                 // places by one                       
                                                 if                                     (                                     0                                     < extraOnes)                       
                                                 printRec(number +                                     "0"                                     , extraOnes -                                     1                                     ,                       
                                                 remainingPlaces -                                     1                                     );                       
                                                 }                       
           
                                                 static                                     void                                     printNums(                                     int                                     n)                       
                                                 {                       
                                                 String str =                                     ""                                     ;                       
                                                 printRec(str,                                     0                                     , n);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     4                                     ;                       
                                   
                                                 // Function call                       
                                                 printNums(n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m                       

Python3

                         # Python 3 program to print all N-bit binary                       
           
                         # function to generate n digit numbers                       
           
           
                         def                                     printRec(number, extraOnes, remainingPlaces):                       
           
                                                 # if number generated                       
                                                 if                                     (                                     0                                     =                                     =                                     remainingPlaces):                       
                                                 print                                     (number, end                                     =                                     " "                                     )                       
                                                 return                       
           
                                                 # Append 1 at the current number and                       
                                                 # reduce the remaining places by one                       
                                                 printRec(number                                     +                                     "1"                                     , extraOnes                                     +                                     1                                     ,                       
                                                 remainingPlaces                                     -                                     1                                     )                       
           
                                                 # If more ones than zeros, append 0 to                       
                                                 # the current number and reduce the                       
                                                 # remaining places by one                       
                                                 if                                     (                                     0                                     < extraOnes):                       
                                                 printRec(number                                     +                                     "0"                                     , extraOnes                                     -                                     1                                     ,                       
                                                 remainingPlaces                                     -                                     1                                     )                       
           
           
                         def                                     printNums(n):                       
                                                 str                                     =                                     ""                       
                                                 printRec(                                     str                                     ,                                     0                                     , n)                       
           
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 n                                     =                                     4                       
                                   
                                                 # Function call                       
                                                 printNums(n)                       
           
                         # This code is contributed by                       
                         # Surendra_Gangwar                       

C#

                         // C# program to print all N-bit binary                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // function to generate n digit numbers                       
                                                 static                                     void                                     printRec(String number,                       
                                                 int                                     extraOnes,                       
                                                 int                                     remainingPlaces)                       
                                                 {                       
           
                                                 // if number generated                       
                                                 if                                     (0 == remainingPlaces)                       
                                                 {                       
                                                 Console.Write(number +                                     " "                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Append 1 at the current number and                       
                                                 // reduce the remaining places by one                       
                                                 printRec(number +                                     "1"                                     , extraOnes + 1,                       
                                                 remainingPlaces - 1);                       
           
                                                 // If more ones than zeros, append                       
                                                 // 0 to the current number and                       
                                                 // reduce the remaining places                       
                                                 // by one                       
                                                 if                                     (0 < extraOnes)                       
                                                 printRec(number +                                     "0"                                     , extraOnes - 1,                       
                                                 remainingPlaces - 1);                       
                                                 }                       
                                                 static                                     void                                     printNums(                                     int                                     n)                       
                                                 {                       
                                                 String str =                                     ""                                     ;                       
                                                 printRec(str, 0, n);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 4;                       
                                   
                                                 // Function call                       
                                                 printNums(n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal.                       

PHP

                         <?php                       
                         // PHP program to print all N-bit binary                       
           
                         // function to generate n digit numbers                       
                         function                                     printRec(                                     $number                                     ,                                     $extraOnes                                     ,                       
                                                 $remainingPlaces                                     )                       
                         {                       
                                                 // if number generated                       
                                                 if                                     (0 ==                                     $remainingPlaces                                     )                       
                                                 {                       
                                                 echo                                     (                                     $number                                     .                                     " "                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Append 1 at the current number and                       
                                                 // reduce the remaining places by one                       
                                                 printRec(                                     $number                                     .                                     "1"                                     ,                                     $extraOnes                                     + 1,                       
                                                 $remainingPlaces                                     - 1);                       
           
                                                 // If more ones than zeros, append 0 to the                       
                                                 // current number and reduce the remaining                       
                                                 // places by one                       
                                                 if                                     (0 <                                     $extraOnes                                     )                       
                                                 printRec(                                     $number                                     .                                     "0"                                     ,                                     $extraOnes                                     - 1,                       
                                                 $remainingPlaces                                     - 1);                       
                         }                       
           
                         function                                     printNums(                                     $n                                     )                       
                         {                       
                                                 $str                                     =                                     ""                                     ;                       
                                                 printRec(                                     $str                                     , 0,                                     $n                                     );                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 4;                       
           
                         // Function call                       
                         printNums(                                     $n                                     );                       
           
                         // This code is contributed by Mukul Singh.                       

Javascript

                         <script>                       
                         // Javascript program to print all N-bit binary                       
           
                                                 // function to generate n digit numbers                       
                                                 function                                     printRec(number, extraOnes, remainingPlaces)                       
                                                 {                       
                                                 // if number generated                       
                                                 if                                     (0 == remainingPlaces) {                       
                                                 document.write(number +                                     " "                                     );                       
                                                 return                                     ;                       
                                                 }                       
                                   
                                                 // Append 1 at the current number and                       
                                                 // reduce the remaining places by one                       
                                                 printRec(number +                                     "1"                                     , extraOnes + 1,                       
                                                 remainingPlaces - 1);                       
                                   
                                                 // If more ones than zeros, append 0 to the                       
                                                 // current number and reduce the remaining                       
                                                 // places by one                       
                                                 if                                     (0 < extraOnes)                       
                                                 printRec(number +                                     "0"                                     , extraOnes - 1,                       
                                                 remainingPlaces - 1);                       
                                                 }                       
                                   
                                                 function                                     printNums(n)                       
                                                 {                       
                                                 let str =                                     ""                                     ;                       
                                                 printRec(str, 0, n);                       
                                                 }                       
           
                         // driver function                       
           
                                                 let n = 4;                       
                                   
                                                 // Function call                       
                                                 printNums(n);                       
                                   
                         </script>                       

输出

1111 1110 1101 1100 1011 1010

也存在一种非递归解决方案，其思想是直接生成2^N到2^（N-1）范围内的数字，然后只需要满足以下条件的数字：

C++

                         // C++ program to print all N-bit binary                       
                         #include <bits/stdc++.h>                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
           
                         // Function to get the binary representation                       
                         // of the number N                       
                         string getBinaryRep(                                     int                                     N,                                     int                                     num_of_bits)                       
                         {                       
                                                 string r =                                     ""                                     ;                       
                                                 num_of_bits--;                       
                                   
                                                 // loop for each bit                       
                                                 while                                     (num_of_bits >= 0)                       
                                                 {                       
                                                 if                                     (N & (1 << num_of_bits))                       
                                                 r.append(                                     "1"                                     );                       
                                                 else                       
                                                 r.append(                                     "0"                                     );                       
                                                 num_of_bits--;                       
                                                 }                       
                                                 return                                     r;                       
                         }                       
           
                         vector<string> NBitBinary(                                     int                                     N)                       
                         {                       
                                                 vector<string> r;                       
                                                 int                                     first = 1 << (N - 1);                       
                                                 int                                     last = first * 2;                       
                                   
                                                 // generate numbers in the range of (2^N)-1 to 2^(N-1)                       
                                                 // inclusive                       
                                                 for                                     (                                     int                                     i = last - 1; i >= first; --i)                       
                                                 {                       
                                                 int                                     zero_cnt = 0;                       
                                                 int                                     one_cnt = 0;                       
                                                 int                                     t = i;                       
                                                 int                                     num_of_bits = 0;                       
                                   
                                                 // longest prefix check                       
                                                 while                                     (t)                       
                                                 {                       
                                                 if                                     (t & 1)                       
                                                 one_cnt++;                       
                                                 else                       
                                                 zero_cnt++;                       
                                                 num_of_bits++;                       
                                                 t = t >> 1;                       
                                                 }                       
                                   
                                                 // if counts of 1 is greater than                       
                                                 // counts of zero                       
                                                 if                                     (one_cnt >= zero_cnt)                       
                                                 {                       
                                                 // do sub-prefixes check                       
                                                 bool                                     all_prefix_match =                                     true                                     ;                       
                                                 int                                     msk = (1 << num_of_bits) - 2;                       
                                                 int                                     prefix_shift = 1;                       
                                                 while                                     (msk)                       
                                                 {                       
           
                                                 int                                     prefix = (msk & i) >> prefix_shift;                       
                                                 int                                     prefix_one_cnt = 0;                       
                                                 int                                     prefix_zero_cnt = 0;                       
                                                 while                                     (prefix)                       
                                                 {                       
                                                 if                                     (prefix & 1)                       
                                                 prefix_one_cnt++;                       
                                                 else                       
                                                 prefix_zero_cnt++;                       
                                                 prefix = prefix >> 1;                       
                                                 }                       
                                                 if                                     (prefix_zero_cnt > prefix_one_cnt)                       
                                                 {                       
                                                 all_prefix_match =                                     false                                     ;                       
                                                 break                                     ;                       
                                                 }                       
                                                 prefix_shift++;                       
                                                 msk = msk & (msk << 1);                       
                                                 }                       
                                                 if                                     (all_prefix_match)                       
                                                 {                       
                                                 r.push_back(getBinaryRep(i, num_of_bits));                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     r;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 4;                       
                                   
                                                 // Function call                       
                                                 vector<string> results = NBitBinary(n);                       
                                                 for                                     (                                     int                                     i = 0; i < results.size(); ++i)                       
                                                 cout << results[i] <<                                     " "                                     ;                       
                                                 cout << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print all N-bit binary                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
                         class                                     GFG                       
                         {                       
           
                                                 // Function to get the binary representation                       
                                                 // of the number N                       
                                                 static                                     String getBinaryRep(                                     int                                     N,                                     int                                     num_of_bits)                       
                                                 {                       
                                                 String r =                                     ""                                     ;                       
                                                 num_of_bits--;                       
           
                                                 // loop for each bit                       
                                                 while                                     (num_of_bits >=                                     0                                     )                       
                                                 {                       
                                                 if                                     ((N & (                                     1                                     << num_of_bits))!=                                     0                                     )                       
                                                 r +=                                     "1"                                     ;                       
                                                 else                       
                                                 r +=                                     "0"                                     ;                       
                                                 num_of_bits--;                       
                                                 }                       
                                                 return                                     r;                       
                                                 }                       
           
                                                 static                                     ArrayList<String> NBitBinary(                                     int                                     N)                       
                                                 {                       
                                                 ArrayList<String> r =                                     new                                     ArrayList<String>();                       
                                                 int                                     first =                                     1                                     << (N -                                     1                                     );                       
                                                 int                                     last = first *                                     2                                     ;                       
           
                                                 // generate numbers in the range of (2^N)-1 to 2^(N-1)                       
                                                 // inclusive                       
                                                 for                                     (                                     int                                     i = last -                                     1                                     ; i >= first; --i)                       
                                                 {                       
                                                 int                                     zero_cnt =                                     0                                     ;                       
                                                 int                                     one_cnt =                                     0                                     ;                       
                                                 int                                     t = i;                       
                                                 int                                     num_of_bits =                                     0                                     ;                       
           
                                                 // longest prefix check                       
                                                 while                                     (t >                                     0                                     )                       
                                                 {                       
                                                 if                                     ((t &                                     1                                     ) !=                                     0                                     )                       
                                                 one_cnt++;                       
                                                 else                       
                                                 zero_cnt++;                       
                                                 num_of_bits++;                       
                                                 t = t >>                                     1                                     ;                       
                                                 }                       
           
                                                 // if counts of 1 is greater than                       
                                                 // counts of zero                       
                                                 if                                     (one_cnt >= zero_cnt)                       
                                                 {                       
                                                 // do sub-prefixes check                       
                                                 boolean                                     all_prefix_match =                                     true                                     ;                       
                                                 int                                     msk = (                                     1                                     << num_of_bits) -                                     2                                     ;                       
                                                 int                                     prefix_shift =                                     1                                     ;                       
                                                 while                                     (msk >                                     0                                     )                       
                                                 {                       
           
                                                 int                                     prefix = (msk & i) >> prefix_shift;                       
                                                 int                                     prefix_one_cnt =                                     0                                     ;                       
                                                 int                                     prefix_zero_cnt =                                     0                                     ;                       
                                                 while                                     (prefix >                                     0                                     )                       
                                                 {                       
                                                 if                                     ((prefix &                                     1                                     )!=                                     0                                     )                       
                                                 prefix_one_cnt++;                       
                                                 else                       
                                                 prefix_zero_cnt++;                       
                                                 prefix = prefix >>                                     1                                     ;                       
                                                 }                       
                                                 if                                     (prefix_zero_cnt > prefix_one_cnt)                       
                                                 {                       
                                                 all_prefix_match =                                     false                                     ;                       
                                                 break                                     ;                       
                                                 }                       
                                                 prefix_shift++;                       
                                                 msk = msk & (msk <<                                     1                                     );                       
                                                 }                       
                                                 if                                     (all_prefix_match)                       
                                                 {                       
                                                 r.add(getBinaryRep(i, num_of_bits));                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     r;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
           
                                                 int                                     n =                                     4                                     ;                       
           
                                                 // Function call                       
                                                 ArrayList<String> results = NBitBinary(n);                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < results.size(); ++i)                       
                                                 System.out.print(results.get(i)+                                     " "                                     );                       
                                                 System.out.println();                       
                                                 }                       
                         }                       
           
                         // This code is contributed by avanitrachhadiya2155                       

Python3

                         # Python3 program to print                       
                         # all N-bit binary                       
           
                         # Function to get the binary                       
                         # representation of the number N                       
                         def                                     getBinaryRep(N, num_of_bits):                       
           
                                                 r                                     =                                     "";                       
                                                 num_of_bits                                     -                                     =                                     1                       
                                   
                                                 # loop for each bit                       
                                                 while                                     (num_of_bits >                                     =                                     0                                     ):                       
                                                 if                                     (N & (                                     1                                     << num_of_bits)):                       
                                                 r                                     +                                     =                                     (                                     "1"                                     );                       
                                                 else                                     :                       
                                                 r                                     +                                     =                                     (                                     "0"                                     );                       
                                                 num_of_bits                                     -                                     =                                     1                       
                                   
                                                 return                                     r;                       
           
                         def                                     NBitBinary(N):                       
           
                                                 r                                     =                                     []                       
                                                 first                                     =                                     1                                     << (N                                     -                                     1                                     );                       
                                                 last                                     =                                     first                                     *                                     2                                     ;                       
                                   
                                                 # generate numbers in the range                       
                                                 # of (2^N)-1 to 2^(N-1) inclusive                       
                                                 for                                     i                                     in                                     range                                     (last                                     -                                     1                                     ,                       
                                                 first                                     -                                     1                                     ,                                     -                                     1                                     ):                       
                                                 zero_cnt                                     =                                     0                                     ;                       
                                                 one_cnt                                     =                                     0                                     ;                       
                                                 t                                     =                                     i;                       
                                                 num_of_bits                                     =                                     0                                     ;                       
                                   
                                                 # longest prefix check                       
                                                 while                                     (t):                       
                                                 if                                     (t &                                     1                                     ):                       
                                                 one_cnt                                     +                                     =                                     1                       
                                                 else                                     :                       
                                                 zero_cnt                                     +                                     =                                     1                       
                                                 num_of_bits                                     +                                     =                                     1                       
                                                 t                                     =                                     t >>                                     1                                     ;                       
                                   
                                                 # if counts of 1 is greater                       
                                                 # than counts of zero                       
                                                 if                                     (one_cnt >                                     =                                     zero_cnt):                       
                                   
                                                 # do sub-prefixes check                       
                                                 all_prefix_match                                     =                                     True                                     ;                       
                                                 msk                                     =                                     (                                     1                                     << num_of_bits)                                     -                                     2                                     ;                       
                                                 prefix_shift                                     =                                     1                                     ;                       
                                   
                                                 while                                     (msk):                       
                                                 prefix                                     =                                     ((msk & i) >>                       
                                                 prefix_shift);                       
                                                 prefix_one_cnt                                     =                                     0                                     ;                       
                                                 prefix_zero_cnt                                     =                                     0                                     ;                       
                                   
                                                 while                                     (prefix):                       
                                                 if                                     (prefix &                                     1                                     ):                       
                                                 prefix_one_cnt                                     +                                     =                                     1                       
                                                 else                                     :                       
                                                 prefix_zero_cnt                                     +                                     =                                     1                       
                                                 prefix                                     =                                     prefix >>                                     1                                     ;                       
                                   
                                                 if                                     (prefix_zero_cnt >                       
                                                 prefix_one_cnt):                       
                                                 all_prefix_match                                     =                                     False                                     ;                       
                                                 break                                     ;                       
                                   
                                                 prefix_shift                                     +                                     =                                     1                       
                                                 msk                                     =                                     msk & (msk <<                                     1                                     );                       
                                   
                                                 if                                     (all_prefix_match):                       
                                                 r.append(getBinaryRep(i,                       
                                                 num_of_bits));                       
                                                 return                                     r                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                   
                                                 n                                     =                                     4                                     ;                       
                                   
                                                 # Function call                       
                                                 results                                     =                                     NBitBinary(n);                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (results)):                       
                                                 print                                     (results[i],                       
                                                 end                                     =                                     " "                                     )                       
                                                 print                                     ()                       
                                   
                         # This code is contributed by Chitranayal                       

C#

                         // C# program to print all N-bit binary                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG{                       
                                   
                         // Function to get the binary representation                       
                         // of the number N                       
                         static                                     string                                     getBinaryRep(                                     int                                     N,                                     int                                     num_of_bits)                       
                         {                       
                                                 string                                     r =                                     ""                                     ;                       
                                                 num_of_bits--;                       
                                   
                                                 // loop for each bit                       
                                                 while                                     (num_of_bits >= 0)                       
                                                 {                       
                                                 if                                     ((N & (1 << num_of_bits)) != 0)                       
                                                 r +=                                     "1"                                     ;                       
                                                 else                       
                                                 r +=                                     "0"                                     ;                       
                                   
                                                 num_of_bits--;                       
                                                 }                       
                                                 return                                     r;                       
                         }                       
                                   
                         static                                     List<                                     string                                     > NBitBinary(                                     int                                     N)                       
                         {                       
                                                 List<                                     string                                     > r =                                     new                                     List<                                     string                                     >();                       
                                                 int                                     first = 1 << (N - 1);                       
                                                 int                                     last = first * 2;                       
                                   
                                                 // Generate numbers in the range of (2^N)-1 to 2^(N-1)                       
                                                 // inclusive                       
                                                 for                                     (                                     int                                     i = last - 1; i >= first; --i)                       
                                                 {                       
                                                 int                                     zero_cnt = 0;                       
                                                 int                                     one_cnt = 0;                       
                                                 int                                     t = i;                       
                                                 int                                     num_of_bits = 0;                       
                                   
                                                 // longest prefix check                       
                                                 while                                     (t > 0)                       
                                                 {                       
                                                 if                                     ((t & 1) != 0)                       
                                                 one_cnt++;                       
                                                 else                       
                                                 zero_cnt++;                       
                                   
                                                 num_of_bits++;                       
                                                 t = t >> 1;                       
                                                 }                       
                                   
                                                 // If counts of 1 is greater than                       
                                                 // counts of zero                       
                                                 if                                     (one_cnt >= zero_cnt)                       
                                                 {                       
                                   
                                                 // Do sub-prefixes check                       
                                                 bool                                     all_prefix_match =                                     true                                     ;                       
                                                 int                                     msk = (1 << num_of_bits) - 2;                       
                                                 int                                     prefix_shift = 1;                       
                                   
                                                 while                                     (msk > 0)                       
                                                 {                       
                                                 int                                     prefix = (msk & i) >> prefix_shift;                       
                                                 int                                     prefix_one_cnt = 0;                       
                                                 int                                     prefix_zero_cnt = 0;                       
                                   
                                                 while                                     (prefix > 0)                       
                                                 {                       
                                                 if                                     ((prefix & 1)!=0)                       
                                                 prefix_one_cnt++;                       
                                                 else                       
                                                 prefix_zero_cnt++;                       
                                   
                                                 prefix = prefix >> 1;                       
                                                 }                       
                                                 if                                     (prefix_zero_cnt > prefix_one_cnt)                       
                                                 {                       
                                                 all_prefix_match =                                     false                                     ;                       
                                                 break                                     ;                       
                                                 }                       
                                                 prefix_shift++;                       
                                                 msk = msk & (msk << 1);                       
                                                 }                       
                                                 if                                     (all_prefix_match)                       
                                                 {                       
                                                 r.Add(getBinaryRep(i, num_of_bits));                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     r;                       
                         }                       
           
                         // Driver code                       
                         static                                     public                                     void                                     Main()                       
                         {                       
                                                 int                                     n = 4;                       
                                   
                                                 // Function call                       
                                                 List<                                     string                                     > results = NBitBinary(n);                       
                                                 for                                     (                                     int                                     i = 0; i < results.Count; ++i)                       
                                                 Console.Write(results[i] +                                     " "                                     );                       
                                   
                                                 Console.WriteLine();                       
                         }                       
                         }                       
           
                         // This code is contributed by rag2127                       

Javascript

                         <script>                       
                                                 // Javascript program to print all N-bit binary                       
                                   
                                                 // Function to get the binary representation                       
                                                 // of the number N                       
                                                 function                                     getBinaryRep(N, num_of_bits)                       
                                                 {                       
                                                 let r =                                     ""                                     ;                       
                                                 num_of_bits--;                       
           
                                                 // loop for each bit                       
                                                 while                                     (num_of_bits >= 0)                       
                                                 {                       
                                                 if                                     ((N & (1 << num_of_bits))!=0)                       
                                                 r +=                                     "1"                                     ;                       
                                                 else                       
                                                 r +=                                     "0"                                     ;                       
                                                 num_of_bits--;                       
                                                 }                       
                                                 return                                     r;                       
                                                 }                       
           
                                                 function                                     NBitBinary(N)                       
                                                 {                       
                                                 let r = [];                       
                                                 let first = 1 << (N - 1);                       
                                                 let last = first * 2;                       
           
                                                 // generate numbers in the range of (2^N)-1 to 2^(N-1)                       
                                                 // inclusive                       
                                                 for                                     (let i = last - 1; i >= first; --i)                       
                                                 {                       
                                                 let zero_cnt = 0;                       
                                                 let one_cnt = 0;                       
                                                 let t = i;                       
                                                 let num_of_bits = 0;                       
           
                                                 // longest prefix check                       
                                                 while                                     (t > 0)                       
                                                 {                       
                                                 if                                     ((t & 1) != 0)                       
                                                 one_cnt++;                       
                                                 else                       
                                                 zero_cnt++;                       
                                                 num_of_bits++;                       
                                                 t = t >> 1;                       
                                                 }                       
           
                                                 // if counts of 1 is greater than                       
                                                 // counts of zero                       
                                                 if                                     (one_cnt >= zero_cnt)                       
                                                 {                       
                                                 // do sub-prefixes check                       
                                                 let all_prefix_match =                                     true                                     ;                       
                                                 let msk = (1 << num_of_bits) - 2;                       
                                                 let prefix_shift = 1;                       
                                                 while                                     (msk > 0)                       
                                                 {                       
           
                                                 let prefix = (msk & i) >> prefix_shift;                       
                                                 let prefix_one_cnt = 0;                       
                                                 let prefix_zero_cnt = 0;                       
                                                 while                                     (prefix > 0)                       
                                                 {                       
                                                 if                                     ((prefix & 1)!=0)                       
                                                 prefix_one_cnt++;                       
                                                 else                       
                                                 prefix_zero_cnt++;                       
                                                 prefix = prefix >> 1;                       
                                                 }                       
                                                 if                                     (prefix_zero_cnt > prefix_one_cnt)                       
                                                 {                       
                                                 all_prefix_match =                                     false                                     ;                       
                                                 break                                     ;                       
                                                 }                       
                                                 prefix_shift++;                       
                                                 msk = msk & (msk << 1);                       
                                                 }                       
                                                 if                                     (all_prefix_match)                       
                                                 {                       
                                                 r.push(getBinaryRep(i, num_of_bits));                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     r;                       
                                                 }                       
                                   
                                                 let n = 4;                       
                                   
                                                 // Function call                       
                                                 let results = NBitBinary(n);                       
                                                 for                                     (let i = 0; i < results.length; ++i)                       
                                                 document.write(results[i]+                                     " "                                     );                       
                                                 document.write(                                     "</br>"                                     );                       
           
                         // This code is contributed by mukesh07.                       
                         </script>                       

输出

1111 1110 1101 1100 1011 1010

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

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

THE END

技术文章