# How to program all possibility in an array?

## Recommended Posts

Sorry noob question (started learning programming on my own last week). I am learning C on my own, and want to do this as personal practice, but couldn't figure it out. I wish to have a file and populate it with this: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 (which is all combination that is possible with 0 and 1 as values). how do I go about it? thank you.

##### Share on other sites
jyk    2094
I'm assuming this is just an exercise you're doing and not an actual homework problem...

Anyway, here's a hint. What you've shown there are the binary representations of the integers in the range [0, 15]. So, you can generate those patterns by iterating over the integers in that range and using bitmasking to determine, for each, which bits are set to '1' and which bits are set to '0'.

##### Share on other sites
hello,

no it's not homework, i'm studying programming on my own as hobby.

how to do bitmasking thing?

##### Share on other sites
jyk    2094
Quote:
 how to do bitmasking thing?
Google/search for 'c bit masking', 'c bitwise operators', etc.

There are other ways you could generate that sequence as well, such as a loop or set of (possibly implied) nested loops that iterated over all of the permutations.

##### Share on other sites
hello,

if i use loops within loops, for the sample above, i would need 4 loops right?

what if i need to populate something with 10 consecutive numbers (instead of the 4 numbers above where possible values are 0 and 1), then i need 10 loops? it's not efficient i think?

##### Share on other sites
smitty1276    560
Count from 1 to the number you need, then change their base to whatever you need.

##### Share on other sites
lpcstr    127
Quote:
Original post by jyk
Quote:
 how to do bitmasking thing?
Google/search for 'c bit masking', 'c bitwise operators', etc.

There are other ways you could generate that sequence as well, such as a loop or set of (possibly implied) nested loops that iterated over all of the permutations.

Correct me if I'm wrong, but wouldn't bit masking with logical operators be more of a C approach? In C++ I think you would define a union that contains an integer and a bit field structure.

Something like:

struct Bitfield{	bool a : 1;	bool b : 1;	bool c : 1;	bool d : 1;	bool e : 1;	bool f : 1;	bool g : 1;	bool h : 1;};union ByteToBits{	char Byte;	Bitfield Bits;};

Or at least something to that effect.

##### Share on other sites
Zipster    2359
Quote:
 Original post by lpcstrCorrect me if I'm wrong, but wouldn't bit masking with logical operators be more of a C approach? In C++ I think you would define a union that contains an integer and a bit field structure.Something like:Or at least something to that effect.

Actually that would still be C. In C++ you'd make heavy use of templates just because you can:

template<size_t N>class ToBinary {};template<size_t N>std::ostream& operator<<(std::ostream& str, const ToBinary<N>&){	str << ToBinary<N/2>();	str << (N & 1) ? '1' : '0';	return str;}template<>std::ostream& operator<<(std::ostream& str, const ToBinary<0>&){	return str;}template<size_t N>class RangeToBinary {};template<size_t N>std::ostream& operator<<(std::ostream& str, const RangeToBinary<N>&){	str << RangeToBinary<N-1>();	str << ToBinary<N>() << std::endl;	return str;}template<>std::ostream& operator<<(std::ostream& str, const RangeToBinary<0>&){	return str;}int main(){	std::cout << RangeToBinary<500>();}

Note: The larger your range, the angrier your compiler gets as it has to expand all the templates :) You could also modify the code a bit to add zero padding but meh.

##### Share on other sites
jyk    2094
Quote:
 Original post by lpcstrCorrect me if I'm wrong, but wouldn't bit masking with logical operators be more of a C approach?
Quote:
 Original post by helloworld123I am learning C on my own...
Emphasis added, of course :)

Anyway, the bitmasking approach is just one way of doing what the OP asked; it's not necessarily the 'best' or most elegant way. (Personally, I'd probably use a loop, which I also suggested.)

##### Share on other sites
alvaro    21246
You can also use backtracking, which is a mechanism that can be adapted for many other enumeration problems.

#include <stdio.h>int array[4];void backtrace(int n) {  if (n==4) {    for (int i=0; i<4; ++i)      printf("%d",array[i]);    printf("\n");  }  else {    for (array[n]=0; array[n]<2; ++array[n])      backtrace(n+1);  }}int main() {  backtrace(0);}

##### Share on other sites
BrianLarsen    100
alternatively,....

the feilds are 8,4,2,1 in value

char MyString[4];
int MyValue
int WorkingValue

for (MyValue = 0 ; MyValue < 16 ; MyValue++)
{
WorkingValue = MyValue;
if (WorkingValue > 8)
{
MyString[0] = "1";
WorkingValue = WorkingValue - 8;
}else {
MyString[0] = "0" ;
}

// handle remaining fields

MyString[4] = 0; // Null terminate!

// String ready for printing or saving to file....

}

##### Share on other sites
alvaro    21246
Quote:
 Original post by BrianLarsenchar MyString[4];...MyString[4] = 0; // Null terminate!

The comment should be // Undefined behavior!

##### Share on other sites
Zahlman    1682
Quote:
 Original post by helloworld123hello,if i use loops within loops, for the sample above, i would need 4 loops right?what if i need to populate something with 10 consecutive numbers (instead of the 4 numbers above where possible values are 0 and 1), then i need 10 loops? it's not efficient i think?

There's no reason to nest loops for each bit.

Instead, have one loop which loops over the numbers and figure out which bits are set for each number (using a second loop for each bit-position).

##### Share on other sites
DevFred    840
You can also treat the number as a string and do the increment yourself. Simply start on the right and flip the first bit. If it flips to 0, continue with the left neighbor. If you cross the left end, you have enumerated all possibilities.
#include <stdio.h>void generate_four(){    char array[] = {0, '0', '0', '0', '0', 0}, *p;    do    {        puts(array + 1);        for (p = array + 4; *p && (*p ^= 1) == '0'; --p)        {}    } while (*p);}

If the length isn't known until runtime, the array allocation and initialization is a little more complicated:
#include <stdlib.h>#include <string.h>void generate(size_t length){    char *array, *p;    array = malloc(length + 2);    if (!array) return;    array[0] = 0;    memset(array + 1, '0', length);    array[length + 1] = 0;    do    {        puts(array + 1);        for (p = array + length; *p && (*p ^= 1) == '0'; --p)        {}    } while (*p);    free(array);}

##### Share on other sites
DevFred    840
By the way, functional languages are made for these kinds of problems:
poss 0 = [""]poss n = map ('0':) rest ++ map ('1':) rest where rest = poss (n-1)> poss 4["0000","0001","0010","0011","0100","0101","0110","0111", "1000","1001","1010","1011","1100","1101","1110","1111"]

##### Share on other sites
Zahlman    1682
Indeed. That might look more familiar to some people spelled in Python:

def poss(n):  if n == 0: return ['']  rest = poss(n - 1)  return ['0' + x for x in rest] + ['1' + x for x in rest]

##### Share on other sites
taz0010    277
You can use cout to output in binary, but this is pretty much cheating. There's a simple algorithm for converting to binary that goes like this:

Divide the number by 2. If there's a remainder, output 1. If no remainder, output 0
Throw away fractional part and repeat process until the number equals 0

This gives the binary value, but in reverse order. If you output to a string, you can just call std::reverse to put it in the right order.

To come up with the "best" method, you can take advantage of the fact that checking if an integer is divisible by 2 is very fast. Just bitwise AND with the value 1, where a result of zero indicates no remainder. You can divide the number by 2 and discard the remainder simply by bit shifting, but if you use an actual division, the compiler will optimise with the faster bit shift operation automatically.

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