CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 21
  1. #1
    Join Date
    Apr 2007
    Posts
    87

    All combinations of 0's and 1's in 128 bit character array?

    Hi!

    I need to generate a character array of all possible values for a known value of zeros.

    i.e. If n=1, I need to somehow cycle through all 128 character arrays with one zero in it.

    Code:
    From: 
    unsigned char key128[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE};
    To:
    unsigned char key128[] = {0x7F,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF};
    Likewise, if n=2, I need to loop through all possible combinations of key128[] with two zero's.

    Any idea of how to go about this? I figure for n=1 I could just bit shift to the left every time, but I don't even know how to do that with a character array.

    Thanks!

  2. #2
    Join Date
    Oct 2009
    Posts
    577

    Smile Re: All combinations of 0's and 1's in 128 bit character array?

    I think you need to clarify your requirement.

    All combinations of 0's and 1's in 128 bit is 2^128 combinations what is about 3.40e+38.

    Even if you would mean digits, i. e. 8bit characters within the 16-byte char array. it would be 2^16 == 65536 combinations.


    Then, what do you mean by ' I need to somehow cycle through all 128 character arrays' ? Where do you have 128 arrays? Do you mean bits?

    Finally, what is the 'From' and 'To' in your code sample and why should a 0xFF turn to 0x7F? If you were searching for 0 bits you won't find one in 0xFF cause all bits were 1.

    Regards, Alex

  3. #3
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588

    Re: All combinations of 0's and 1's in 128 bit character array?

    Hi,

    You can simply use next_permutation from STL algorithms. This is an example of how you would use it. The data structures are not the same as yours, but you should be able to adapt that with a bit vector or modifying the output.
    Code:
    #include <algorithm>
    #include <vector>
    #include <iostream>
    
    
    void output_vector(const std::vector<int> &v)
    {
    	for (size_t i = 0; i < v.size(); ++i) {
    		std::cout << v[i];
    	}
    	std::cout << std::endl;
    }
    
    
    void test_perm(size_t c, size_t n)
    {
    	std::vector<int> v;
    
    	for (size_t i = 0; i < n; ++i) {
    		if (i < c) {
    			v.push_back(0);
    		} else {
    			v.push_back(1);
    		}
    	}
    	output_vector(v);
    	while (std::next_permutation(v.begin(), v.end())) {
    		output_vector(v);
    	}
    }
    
    int main()
    {
    	test_perm(2, 10);
    	return 0;
    }
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  4. #4
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: All combinations of 0's and 1's in 128 bit character array?

    I was also going to propose next permutation, but I thought he wanted something more like this:

    Code:
    0000
    0001
    0010
    0011
    0100
    0101
    0110
    ...
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  5. #5
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: All combinations of 0's and 1's in 128 bit character array?

    Quote Originally Posted by monarch_dodra View Post
    I was also going to propose next permutation, but I thought he wanted something more like this:

    Code:
    0000
    0001
    0010
    0011
    0100
    0101
    0110
    ...
    Let's see. That's 0, 1, 2, 3, 4, 5, 6... Maybe there's a pattern there.

  6. #6
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: All combinations of 0's and 1's in 128 bit character array?

    Quote Originally Posted by GCDEF View Post
    Let's see. That's 0, 1, 2, 3, 4, 5, 6... Maybe there's a pattern there.


    Yeah, I also saw that.

    But if you have a vector of chars, it's not as simple as "++myVectorChar". I supposed that's what the user wanted...
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  7. #7
    Join Date
    Apr 2007
    Posts
    87

    Re: All combinations of 0's and 1's in 128 bit character array?

    Yeah, I wanted more something like this (but with a character array like the one in the first post):

    With n=1 zero:
    Code:
    1111110
    1111101
    1111011
    1110111
    1101111
    1011111
    0111111
    With n=2 zeros:

    Code:
    1111100
    1111010
    1111001
    .....
    0011111
    Obviously I'm not going to go up to n=64 zero's (since that would be impossible), but something like n=4 or n=5 zeros would be the limit. Still not sure how to do this with character arrays though :s
    Last edited by Lucky75; July 21st, 2010 at 11:48 AM.

  8. #8
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: All combinations of 0's and 1's in 128 bit character array?

    In that case, I recommend you use a bitset. This will allow for easier bit manipulation.

    bitsets have a method called "to_string" you can use to convert your bits into a string. from there, just call string's data() or c_str member functions, and you are done.

    It takes some operations, but has the advantage of taking about 5 lines of code to write.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  9. #9
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: All combinations of 0's and 1's in 128 bit character array?

    I'm fairly sure next_permutation is what you want here.

  10. #10
    Join Date
    Apr 2007
    Posts
    87

    Re: All combinations of 0's and 1's in 128 bit character array?

    It looks like what Yves M has works. I suppose doing the same thing on a bitset would work as well, although im not sure which one would be better or what to pass to the next_permutation with the bitset one.

    Regardless, the problem seems to be getting the vector back into a 16 byte character array. Is there a clean way to go about that?


    really it should look like (but 16 bytes long):

    Code:
    0xFF 0xFF 0xFF 0xFE
    0xFF 0xFF 0xFF 0xFD
    0xFF 0xFF 0xFF 0xFB
    0xFF 0xFF 0xFF 0xF7
    0xFF 0xFF 0xFF 0xEF
    ...
    0xBF 0xFF 0xFF 0xFF
    0x7F 0xFF 0xFF 0xFF
    0xFF 0xFF 0xFF 0xFF
    Thanks for all the responses everyone!
    Last edited by Lucky75; July 21st, 2010 at 01:33 PM.

  11. #11
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: All combinations of 0's and 1's in 128 bit character array?

    Just use next_permutation directly on the array. In this case there's no real need to get vectors involved.

  12. #12
    Join Date
    Oct 2009
    Posts
    577

    Smile Re: All combinations of 0's and 1's in 128 bit character array?

    Quote Originally Posted by Lucky75 View Post
    It looks like what Yves M has works. I suppose doing the same thing on a bitset would work as well, although im not sure which one would be better or what to pass to the next_permutation with the bitset one.

    Regardless, the problem seems to be getting the vector back into a 16 byte character array. Is there a clean way to go about that?


    really it should look like (but 16 bytes long):

    Code:
    0xFF 0xFF 0xFF 0xFE
    0xFF 0xFF 0xFF 0xFD
    0xFF 0xFF 0xFF 0xFB
    0xFF 0xFF 0xFF 0xF7
    0xFF 0xFF 0xFF 0xEF
    ...
    0xBF 0xFF 0xFF 0xFF
    0x7F 0xFF 0xFF 0xFF
    0xFF 0xFF 0xFF 0xFF
    Thanks for all the responses everyone!

    To get the output you wanted you can modify the output_vector function of the code Yves M had posted:

    Code:
    void output_vector(const std::vector<int> &v)
    {
          for (size_t i = 0; i < v.size(); ++i) {
               std::cout << " 0x" << std::hex << std::setw(2) << std::setfill('0') << (int)v[i];
          }
          std::cout << std::endl;
    }
    You would need to include <iomanip> for the manipulator objects hex, setw and setfill.

    Regards, Alex
    Last edited by itsmeandnobodyelse; July 22nd, 2010 at 02:04 AM.

  13. #13
    Join Date
    Apr 2007
    Posts
    87

    Re: All combinations of 0's and 1's in 128 bit character array?

    Mhm, that would work fine if I was just printing, but I need to actually store it in a 16 byte character array and pass it to another function.

    And calling next_permutation on the character array directly would just swap the different combinations of bytes instead of the individual bits, wouldn't it??

  14. #14
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: All combinations of 0's and 1's in 128 bit character array?

    Code:
    #include <iostream>
    #include <iomanip>
    #include <vector>
    #include <bitset>
    #include <string>
    #include <algorithm>
    #include <climits>
    #include <iterator>
    
    template <typename CharIt_t>
    void hex_char_output(CharIt_t first, CharIt_t last)
    {
        using std::ios;
    
        std::cout.setf ( ios::hex, ios::basefield );
        std::cout.setf ( ios::internal, ios::adjustfield );
        std::cout.fill('0');
        for ( ; first != last; ++first )
        {
            //Add 0x by hand to avoid for null values
            std::cout << "0x" << std::setw(2) <<
                    static_cast<unsigned int>(static_cast<unsigned char>(*first)) << //Cast to int to see numeric values, cast to unsigned char first for proper padding
                    ", ";
        }
    }
    
    int main()
    {
        const size_t nBytes = 4;
        const size_t nBits  = nBytes * CHAR_BIT;
    
        unsigned char myChars[nBytes];
    
        std::vector<char> myBits(nBits, 1);
        myBits[nBits-1] = 0;
        myBits[nBits-2] = 0;
    
        //hex_char_output(myChars, myChars+nBytes);
        //std::cout << std::endl;
    
        bool result = true; //Use a result so we can see the first iteration without permutating
        while ( result )
        {
            std::bitset<nBits> myBitset;
    
            //Can't use std::copy because of bitset
            for ( size_t i = 0; i < nBits; ++i )
            {
                myBitset[i] = myBits[i];
                std::cout << myBitset[i];
            }
            std::cout << ": ";
    
            for ( size_t i = 0; i<nBytes; ++i)
            {
                unsigned long myLong = myBitset.to_ulong();
                unsigned char myChar = static_cast<unsigned char>(myLong);
                myChars[i] = myChar;
                myBitset>>=CHAR_BIT;
            }
    
            hex_char_output(myChars, myChars+nBytes);
            std::cout << std::endl;
    
            result = std::next_permutation(myBits.rbegin(), myBits.rend());
        }
    }
    Step 1 : Fill a vector
    Step 2 : Permutate the vector
    Step 3 : Copy into bitset
    Step 4 : use to_ulong to recover an integer. Cast and shift to fill your array.

    If you had any particular needs in the shift order, or if you wanted your char array to mimic some specific memory layout (small/big endian), I'll let you figure it out.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  15. #15
    Join Date
    Oct 2009
    Posts
    577

    Smile Re: All combinations of 0's and 1's in 128 bit character array?

    Quote Originally Posted by Lucky75 View Post
    Mhm, that would work fine if I was just printing, but I need to actually store it in a 16 byte character array and pass it to another function.

    And calling next_permutation on the character array directly would just swap the different combinations of bytes instead of the individual bits, wouldn't it??

    The vector already holds an internal 16-byte elements array.

    If you do

    Code:
         unsigned char * p = (unsigned char *)&v[0];
         some_otherfunction_expecting_a_16bytes_array(p);
    where v is one of the permutations you got the pointer p would point to a 16-elements array.

    If you want to copy the array to fixed-sized char array, you would/could do

    Code:
         unsigned char arr[16] = { '\0' };
         unsigned char * p = (unsigned char *)&v[0];
         memcpy(arr, p, min(sizeof(arr), v.size() * sizeof(v[0])));
    The min is only to make sure that the vector really has 16 elements of type char, same as the arr.

    Regards, Alex
    Last edited by itsmeandnobodyelse; July 22nd, 2010 at 04:27 AM.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured