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!

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

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;
}

---

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
...

---

Quote:

---

Originally Posted by monarch_dodra

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.

Quote:

---

Originally Posted by GCDEF

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...

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

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.

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

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!

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

Quote:

---

Originally Posted by Lucky75

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

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??

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.

Quote:

---

Originally Posted by Lucky75

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

Quote:

---

Originally Posted by itsmeandnobodyelse

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

---

That is all very true, but the problem remains that if you store bytes inside the vector, when you call next_permutation, you will be per mutating bytes, and not bits. Sure, you can recover the chars easily, but they won't be properlly shifted

A good solution would have been to use a vector<bool>, as it stores bit(-like) objects. This would work perfectly if you could write &v[0] on a vector bool, but you can't (at least not to my knowledge).

IMO, it's a lose-lose situation, where you have to get creative and daisy chain several solutions.

Quote:

---

Originally Posted by monarch_dodra

That is all very true, but the problem remains that if you store bytes inside the vector, when you call next_permutation, you will be per mutating bytes, and not bits.

---

So what? Make your container 8x larger, and you'll have logically the same result.

Quote:

---

Originally Posted by Lindley

So what? Make your container 8x larger, and you'll have logically the same result.

---

Yes, if you make your container 8 times larger, you get the desired result, but from there, it's the copying back into the char array that becomes problematic :/

Quote:

---

Originally Posted by itsmeandnobodyelse

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

---

:( the index should be 15 :cry:

Hmm, actually, using bitset instead of a vector and then just memcpying into a char array of length 16 (bytes) works :)

Thanks all!

Yikes. You shouldn't use memcpy() on C++ objects.

If it's just an assignment, whatever. But if you actually intend this code to be portable and robust, that's not a good approach.