Trying to print every combination of bits , given a variable

Question

Lets say combinationlength=4. My logic is create the array {0,0,0,0} add 1 to the last element until first element gets the value 1.Until then if with the addition of 1 the array[3] ends up in a 2 result then make it 0 and then traverse the array(reversed) given a counter variable and every first non 1 element make it 0 while making all elements before the value that first non 1 equal to 0.This is for 8 repetitions.How close am i?Can someone help me finish this?

Also this doesnt run for some reason.Nothing gets printed and ends after 2 seconds.

I just noticed i am skipping a step but anyways.

I want in every iteration to have an array like the sequence.And not added printf("0"); and shortcuts like that.

void print(int combinationlength){
    int i,j,count;
        int a=combinationlength-1;
        int c=combinationlength-1;
        int b;
        int array[4]={0};
        while(array[0]!=1){
            array[a]++;
            if(array[a]==2){
                array[a]=0;
                for(b=a;b<=c-1;b--){
                    if(array[b]==0)
                        array[b]=1;
                }
                c--;
            }
        for(count=0;count<combinationlength;count++){
            printf("%d",array[count]);
        }
        printf("\n");
        }

    return 0;
    }

UPDATED:(also updated my explanation above this ^^ block of code)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int main(){
    int i,j,count;
    int a=4-1;
    int c=4-1;
    int b;
    int array[4]={0};
    while(array[0]!=1){
        array[a]++;
        if(array[a]==2){
            array[a]=0;
            for(b=a-1;b>c-1;b--){
                if(array[b]==0) array[b]=1;
                else array[b]=0;
            }
            c--;
        }
        for(count=0;count<4;count++){
            printf("%d",array[count]);
        }
        printf("\n");
    }
return 0;
}

The hardcoded number 4 is supposed to be the input variable.

Answer 1

So, I'm still not entirely sure I understand what you want. If I understood correctly, you want every combination of bits (i.e. zeros and ones) of a certain length. Doing the additions manually in an array feels very wasteful, so lets instead use what the CPU already has to offer - integer addition.

An example program, printing all the combinations of a certain length would look something like this:

#include <stdio.h>

void print(int len){
    for (unsigned long sortOfAnArray = 0; sortOfAnArray < (1U << len); sortOfAnArray++) {
        for (int i = len - 1; i >= 0; i--) {
            printf("%lu", (sortOfAnArray >> i) & 1);
        }
        printf("\n");
    }
}

int main(void) {
    print(5);
    return 0;
}

To explain the steps, sortOfAnArray is our integer, stored in binary, we add 1 to it on every iteration so that we get the different combinations.

In order to print it, we have to access elements individually, we do this with a combination of a bitshift and logical and (sortOfAnArray >> i) & 1. So, we shift the bits in the array by i to the right, and check if it has a 1 on the first position, in other words, we checked if sortOfAnArray[i]==1 (if this was an array).

We use unsigned due to the standard and long in case you want up to 64 bits available (although long long would be even safer there).

EDIT

To further explain how we extract a bit from the integer.

Assume we have the integer

`unsigned long long foo = 27`

if we look at the bit representation of that, we get 00...011011, where the total number of bits is 64, but there's just a lot of zeros, hence the dots. Now, say we want to know the value of the 1st bit from the right. We can find that out by using the logical and operation

`foo & 1`

This will apply the logical and to every pair of bits at the same position in the two integers (foo and 1), in this case this will give us 1:

foo     -- 00...011011
1       -- 00...000001
foo & 1 -- 00...000001

If foo had 0 as the rightmost bit, the result would instead be 0, so this essentially allows us to read whether the first bit is set to 0 or 1.

How do we generalise this to the other bits?

We have two options, we can either move the bit in the 1 (1 << n shifts the 1 bit n moves to the left), if we use the logical and then, we will get 0 if foo has a 0 in the n-th position or some nonzero value (2^n) if it has a 1.

The other option is to instead shift the bits of foo to the right, the upside of doing this is if foo had a 1 in the n-th position, the result will now be 1 rather than 2^n, whereas if it was 0 the result is still 0. Other than that the two approaches are equivalent.

This is how we come up with the final solution, that is, to access the n-th element (0-based counting) as follows:

(foo >> n) & 1

we move the bits of foo to the right by n and look if the first bit is set to 0 or 1. Essentially, the integer is storing 64 bits (we don't need to use all of them, of course) the same way we would do that in an array, but the approach is much more efficient. Among other things, we don't need to implement our own addition for the array, as you had attempted initially.

Answer 2

An integer already consists (most of the time) of 4 bytes = 32 bits. You can use a simple integer instead of an array.

However printing an integer in binary format is a bit tricky, I used the answer of this question to do it.

#include <stdio.h>

#define BYTE_TO_BINARY_PATTERN "%c%c%c%c%c%c%c%c"
#define BYTE_TO_BINARY(byte)  \
  (byte & 0x80 ? '1' : '0'), \
  (byte & 0x40 ? '1' : '0'), \
  (byte & 0x20 ? '1' : '0'), \
  (byte & 0x10 ? '1' : '0'), \
  (byte & 0x08 ? '1' : '0'), \
  (byte & 0x04 ? '1' : '0'), \
  (byte & 0x02 ? '1' : '0'), \
  (byte & 0x01 ? '1' : '0')

int main(void) {
    int a = 0;
    int limit = 4;

    while( (a & (1 << limit)) == 0)
    {
        printf("0b"BYTE_TO_BINARY_PATTERN"\n", BYTE_TO_BINARY(a));
        a++;
    }
    return 0;
}

Output:

0b00000000
0b00000001
0b00000010
0b00000011
0b00000100
0b00000101
0b00000110
0b00000111
0b00001000
0b00001001
0b00001010
0b00001011
0b00001100
0b00001101
0b00001110
0b00001111

Little explanation:

In the while loop I use a so called bit mask. (1 << limit) results in a binary 1 at the position limit, so in this case it would be 0b00010000. With the binary & I check if a has that bit, if yes the while loop ends.

Answer 3

Whenever I have to do something involving iteration over combinations, I automatically think of Grey Codes / reverse binary coding. Below is my own implementation (it uses a different formula than the wiki, but still covers all the values). Note they won't be in order, but it does cover all combinations 0->2^n-1 and it is very fast since it only needs to change one value each time.

#include <stdio.h>

int main(int argc, char** argv) {
    unsigned int length = 4;
    unsigned int array[4] = {0, 0, 0, 0};

    int i, j;
    for (i = 0; i < 1 << length; i++) {
        array[__builtin_ctz(i)] ^= 1;

        printf("Array Values: ");
        for (j = 0; j < length; j++) {
            printf("%d ", array[j]);
        }
        printf("\n");
    }
    return 0;
}

Output:

Array Values: 0 0 0 0 
Array Values: 1 0 0 0 
Array Values: 1 1 0 0 
Array Values: 0 1 0 0 
Array Values: 0 1 1 0 
Array Values: 1 1 1 0 
Array Values: 1 0 1 0 
Array Values: 0 0 1 0 
Array Values: 0 0 1 1 
Array Values: 1 0 1 1 
Array Values: 1 1 1 1 
Array Values: 0 1 1 1 
Array Values: 0 1 0 1 
Array Values: 1 1 0 1 
Array Values: 1 0 0 1 
Array Values: 0 0 0 1

Note I use the __builtin_ctz() method to count trailing zeros quickly. I don't know if its implemented on any other compilers, but GCC supports it.

Answer 4

Your problem statement is confusing:

if with the addition of 1 the array[3] ends up in a 2 result then make it 0 and then traverse the array(reversed) given a counter variable and every first non 1 element make it 0 while making all elements before the value that first non 1 equal to 0.

This basically means you want the first 0 element to remain 0 while making all elements before that first 0 set to 0.

As a consequence, the array contents would alternate between { 0, 0, 0, 0 } and { 0, 0, 0, 1 }, which is probably not the intent.

Let's assume your problem is to simulate a base-2 counter with 4 binary digits and you count from 0 to 8. Your code is a bit too complicated (pun intended ;-). You should simplify and use fewer index variables:

#include <stdio.h>

int main() {
    int i;
    int array[4] = { 0 };

    while (array[0] != 1) {
        for (i = 0; i < 4; i++) {
            printf("%d ", array[i]);
        }
        printf("\n");
        for (i = 4; i-- > 0; ) {
            array[i] += 1;
            if (array[i] == 2) {
                array[i] = 0;
            } else {
                break;
            }
        }
    }
    return 0;
}

Output:

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1

Note how you can write a for loop that counts down from the length of the array, enumerating all valid index values while using the exact length of the array and using a test i-- > 0 that is correct for both signed and unsigned types. This trick is sometimes referred to as the downto operator, not a real operator but one can make it look like one as i --> 0.

EDIT: to print the complete set of binary combinations, keep looping until i is -1:

#include <stdio.h>

int main() {
    int i;
    int array[4] = { 0 };

    for (;;) {
        for (i = 0; i < 4; i++) {
            printf("%d ", array[i]);
        }
        printf("\n");
        for (i = 4; i-- > 0; ) {
            array[i] += 1;
            if (array[i] == 2) {
                array[i] = 0;
            } else {
                break;
            }
        }
        if (i < 0) {
            /* the array is too small, all combinations exhausted */
            break;
        }
    }
    return 0;
}