-
July 21st, 2010, 01:36 AM
#1
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!
-
July 21st, 2010, 01:54 AM
#2
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
-
July 21st, 2010, 04:54 AM
#3
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.
-
July 21st, 2010, 05:13 AM
#4
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.
-
July 21st, 2010, 05:38 AM
#5
Re: All combinations of 0's and 1's in 128 bit character array?
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.
-
July 21st, 2010, 07:11 AM
#6
Re: All combinations of 0's and 1's in 128 bit character array?
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...
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.
-
July 21st, 2010, 11:46 AM
#7
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.
-
July 21st, 2010, 12:24 PM
#8
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.
-
July 21st, 2010, 12:28 PM
#9
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.
-
July 21st, 2010, 01:08 PM
#10
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.
-
July 21st, 2010, 01:59 PM
#11
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.
-
July 22nd, 2010, 01:18 AM
#12
Re: All combinations of 0's and 1's in 128 bit character array?
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
Last edited by itsmeandnobodyelse; July 22nd, 2010 at 02:04 AM.
-
July 22nd, 2010, 03:21 AM
#13
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??
-
July 22nd, 2010, 04:23 AM
#14
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.
-
July 22nd, 2010, 04:25 AM
#15
Re: All combinations of 0's and 1's in 128 bit character array?
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
Last edited by itsmeandnobodyelse; July 22nd, 2010 at 04:27 AM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|