generating binary strings

This is a discussion on generating binary strings within the C Programming forums, part of the General Programming Boards category; Hey folks, I'm in need of some help finding/creating an algorithm to produce all binary strings given some length "n" ...

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    25

    generating binary strings

    Hey folks,

    I'm in need of some help finding/creating an algorithm to produce all binary strings given some length "n"

    It doesn't have to be in C, but you all tend to give good answers so i thought id ask here.

    My initial thought is to start at some pivot
    _0_000 (pivot isolated by _ _)
    and produce every 1/0 for the other bits.
    _0_000
    _0_001
    _0_010

    etc.

    Translating this into actual source is proving quite difficult so I'm curious if anyone knows any permutation algorithms well suited for this problem.

    Thank you!

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,462
    If you need all binary strings of length n, you can simply count from 0 to 2^n - 1. For example, all 3-bit strings:
    0 000
    1 001
    2 010
    3 011
    4 100
    5 101
    6 110
    7 111 <--- 2^3 - 1

    If you are really interested in some permutation-related stuff, so this can extend beyond binary symbols, look at the factoradic (factorial base) number system: Factorial number system - Wikipedia, the free encyclopedia.

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    25
    I'm hoping to extend this binary string stuff to a particular situation.

    If I have an identifier like "abcd" I need to produce every possible split for that such that a split consists of a placement of underscores between individual characters.

    so abcd could split to:
    abcd
    a_b_c_d
    etc.

    Are there any functions for converting ints to binary strings?

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,462
    Not any standard functions. You can write your own easily enough, with a little loop and bit-shifting:
    Code:
    for (i = 1 << n-1; i > 0; i >>= 1) {
        if (num & i)  // single ampersand for bit-wise and
            putchar('1');
        else
            putchar('0');
    }
    To extend it for your situation, with the underscores, you could use a 1 in a given bit position to signify the presence of an underscore and a 0 to signify the lack thereof.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unable to store string's into my Binary Search Tree?
    By twiztidsoulz in forum C Programming
    Replies: 14
    Last Post: 11-03-2009, 03:01 PM
  2. Problems with strings as key in STL maps
    By all_names_taken in forum C++ Programming
    Replies: 3
    Last Post: 01-17-2006, 10:34 AM
  3. Strings and binary
    By Flip in forum C++ Programming
    Replies: 13
    Last Post: 12-04-2005, 12:12 PM
  4. Confused by expression.
    By Hulag in forum C Programming
    Replies: 3
    Last Post: 04-07-2005, 07:52 AM
  5. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 08:09 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21