Jump to content
Renderer

Generate all binary string possibilities of n bits

Recommended Posts

Hi guys! I have a question regarding binary  digits. How can I write an algorithm to generate all the possible binary combinations of n bits long? I konw the basics like 2 bit long binary strings can generate 2 ^ 2 = 4 possible combinations like 00, 01, 10, 00. How am I gonna put this into code? I really have no idea. Thanks in advance! 

Share this post


Link to post
Share on other sites

Here's one way to do it.  Note that this example will only work up to 32 bits because the AutoIt bit operations only work with 32-bit integers.  If you need to work with more bits, you will need a different solution.

display_bit_combinations(4)

Func display_bit_combinations($iNumberOfBits)
    Local $sBits = ""

    ConsoleWrite("Number of bits to display: " & $iNumberOfBits & @CRLF)

    ;Loop thru integers from 0 to 2^bits - 1
    For $i = 0 To (2 ^ $iNumberOfBits) - 1

        ;Loop thru integer's bits from high-order bit to low-order bit
        ;to build the bit string in big-endian

        $sBits = ""
        For $j = $iNumberOfBits - 1 To 0 Step -1
            $sBits &= (BitAND($i, 2 ^ $j) ? "1" : "0")
        Next

        ConsoleWrite($sBits & "b = " & $i & @CRLF)
    Next
EndFunc

Output:

Number of bits to display: 4
0000b = 0
0001b = 1
0010b = 2
0011b = 3
0100b = 4
0101b = 5
0110b = 6
0111b = 7
1000b = 8
1001b = 9
1010b = 10
1011b = 11
1100b = 12
1101b = 13
1110b = 14
1111b = 15

 

Edited by TheXman

Share this post


Link to post
Share on other sites

Increment an integer from 0 to 2ⁿ-1

If you actually need the binary expansion in string form:

Local $n = 9
Local $s = ""
Local $aRes
Local $zeroes = _StringRepeat("0", $n - 1)
For $i = 0 To 2 ^ $n - 1
    $aRes = DllCall("ntdll.dll", "str:cdecl", "_ui64toa", "int64", $i, "str", $s, "int", 2)
    ConsoleWrite(StringRight($zeroes & $aRes[0], $n) & @LF)
Next

 

Edited by jchd

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

Simple:

PrintBits($CmdLine[1],"")

Func PrintBits($iBits, $sBits)
   $iBits-=1
   If $iBits<0 Then
      ConsoleWrite($sBits & @CRLF)
   Else
      For $n=0 To 1
         PrintBits($iBits,$sBits & $n)
      Next
   EndIf
EndFunc

Output:

C:\>bits 4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

C:\>

 


Code hard, but don’t hard code...

Share this post


Link to post
Share on other sites

Even simpler :

Combine("", 4)
Func Combine($Str, $nBit)
  $t = $nBit ? Execute(Combine($Str & 0, $nbit-1) & Combine($Str & 1,$nBit-1)) : ConsoleWrite ($Str & @CRLF)
EndFunc

 

Share this post


Link to post
Share on other sites

The recursion is nice but most users have hard time using it in the general case. Good that you posted it.

OTOH using _ui64toa allows to use any base in [2, 36] with no change (except that I did hardcore the base in the snippet). Of course, recursion can be bent to do it as well.


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites
24 minutes ago, jchd said:

The recursion is nice but most users have hard time using it in the general case.

True.
Please understand I had to post it, even if as purely a defensive measure, as I was not ready to entertain the inevitable smugness of anyone else’s recursive gloating :)
 

Edited by JockoDundee

Code hard, but don’t hard code...

Share this post


Link to post
Share on other sites
16 minutes ago, Nine said:

But it is one more line 

Ah, that makes sense.  I don’t use Scite much, just the compiler, and it doesn’t complain.  Come to think of it, the compiler doesn’t complain about anything really, as long as for every <tag> there’s a </tag>.

Anyway, if you want a real challenge - https://www.autoitscript.com/forum/topic/204426-guess-the-output/

:)


Code hard, but don’t hard code...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...