C - iterate over array of 0s & 1s as if binary number

Question

I need to iterate over an array of n elements (dynamic size thus), for example 4, as if it were a binary number, starting with all zeros ({0,0,0,0}). Every time this needs to increment as if it is binary, {0,0,0,0} -> {0,0,0,1} -> {0,0,1,0} -> {0,0,1,1} -> {0,1,0,0}, etc...

I have trouble generating an algorithm that does so with array values, I thought about using recursion but cannot find the method to do so other than hard-coding in ifs. I suppose I could generate an n-digit number and then apply any algorithm discussed in this post, but that would be inelegant; the OP asked to print n-digit numbers while I need to work with arrays.

It would be great if someone could point me in the right direction.
Context:

int n;
scans("%d", &n);
int *arr = calloc(n, sizeof(int));

I suppose it depends on what your staring point is, and how you want to iterage. for example, do you increment an int and then convert that to the output you require, or do you need to 'parse' the array to find the current value and then increment it? — Neil, Oct 26 '17 at 12:47
@Neil I'm confused by what you mean :) Every time the array is reformed (in a binary incremental manner) I call a function which uses the values from that array, which workings are think unnecessary for this post) — Isaiah, Oct 26 '17 at 12:54

score 4 · Answer 1 · answered Oct 26 '17 at 12:50

4

Algorithm:

Start at the rightmost element.
- If it's a zero, then set it to one and exit
- It must be a one; set it to zero
- If you are at the left-most element, then exit.
- You aren't already at the left-most element; move left one element and repeat.

I'm sorry, I'm not in a position to provide a code sample.

answered Oct 26 '17 at 12:50

hymie

1,982
1
13
18

Wouldn't that just toggle every value? – Isaiah Oct 26 '17 at 12:57
@Isaiah No, it wouldn't. Try it out on paper and see. (If you replace "exit" with "copy the rest of the numbers and you're done", it's the addition algorithm you probably learned in primary school.) – molbdnilo Oct 26 '17 at 13:03
I see, I was confused by the previous terms used :] It's great, thank you! – Isaiah Oct 26 '17 at 16:22

score 1 · Answer 2 · answered Oct 26 '17 at 13:02

What you seem to want to do is implement binary addition (or more precisely a binary counter), which is anyway implemented in the CPU's digital circuit using logic gates. It can be done using combination of logical operations (nand and xor to be exact).

But the most elegant approach according to my sense of elegance would be to use the CPU's innate ability to increment numbers and write a function to decompose a number to a bit array:

void generate_bit_array(unsigned int value, uint8_t *bit_array, unsigned int bit_count) {
    for (unsigned int i=0; i<bit_count; i++) {
        bit_array[i] = value >> (bit_count - i - 1) & 0x01;
    }
}

int main(int argc, void **argv) {
    unsigned int    i;
    uint8_t         my_array[4];

    /* Iterate and regenerate array's content */
    for (i=0; i<4; i++) {
        generate_bit_array(i, my_array, 4);
        /* Do something */
    }

    return 0;
}

Vlad from Moscow · Answer 3 · 2017-10-26T13:42:49.450

If I have understood you correctly then what you need is something like the following

#include <stdio.h>

#define N   4

void next_value( unsigned int a[], size_t n )
{
    unsigned int overflow = 1;

    for ( size_t i = n; i != 0 && overflow; i-- )
    {
        overflow = ( a[i-1] ^= overflow ) == 0;
    }
}

int empty( const unsigned int a[], size_t n )
{
    while ( n && a[n-1] == 0 ) --n;

    return n == 0;
}

int main(void)
{
    unsigned int a[N] = { 0 };

    do 
    {
        for ( size_t i = 0; i < N; i++ ) printf( "%i ", a[i] );
        putchar( '\n' );
        next_value( a, N );
    } while ( !empty( a, N ) );

    return 0;
}

The program output is

Or you can write the function that evaluates a next value such a way that if the next value is equal to 0 then the function returns 0.

For example

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

int next_value( unsigned int a[], size_t n )
{
    unsigned int overflow = 1;

    for ( ; n != 0 && overflow; n-- )
    {
        overflow = ( a[n-1] ^= overflow ) == 0;
    }

    return  overflow == 0;
}

int main(void)
{
    size_t n;

    printf( "Enter the length of the binary number: " );
    if ( scanf( "%zu", &n ) != 1 ) n = 0;

    unsigned int *a = calloc( n, sizeof( unsigned int ) );

    do 
    {
        for ( size_t i = 0; i < n; i++ ) printf( "%i ", a[i] );
        putchar( '\n' );
    } while ( next_value( a, n ) );

    free( a );

    return 0;
}

The program output might look like

Enter the length of the binary number: 3
0 0 0 
0 0 1 
0 1 0 
0 1 1 
1 0 0 
1 0 1 
1 1 0 
1 1 1

score 1 · Accepted Answer · edited Jun 20 '20 at 09:12

Algorithm:

Start at the rightmost element.

If it's a zero, then set it to one and exit

It must be a one; set it to zero

If you are at the left-most element, then exit.

You aren't already at the left-most element; move left one element and repeat.

Here's Hymie's algorithm, I'll try making a code out of it :

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

int my_algo(int *arr, int size) {
  for (int i = size - 1; i >= 0; i--) { // Start at the rightmost element
    if (arr[i] == 0) { // If it's a zero, then set it to one and exit
      arr[i] = 1;
      return 1;
    } else if (arr[i] == 1) { // If it's a one, set it to zero and continue
      arr[i] = 0;
    }
  }
  return 0; // stop the algo if you're at the left-most element
}

int main() {
    int n;
    scanf("%d", &n);
    int *arr = calloc(n, sizeof(int));
    do {
      for (int i = 0; i < n; i++) {
        putchar(arr[i] + '0');
      }
      putchar('\n');
    } while (my_algo(arr, n));
    return (0);
}

This algorithm is dynamic and work with scanf. Here's the result for 4 :

H.S. · Answer 5 · 2017-10-26T13:29:29.193

You can do:

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

void gen_bit_array(int *numarr, int n, int arr_size) {
        if(n > 0) {
                numarr[arr_size-n] = 0;
                gen_bit_array(numarr, n-1, arr_size);
                numarr[arr_size-n] = 1;
                gen_bit_array(numarr, n-1, arr_size);
        } else {
                int i;
                for(i=0; i<arr_size; i++)
                        printf("%d", numarr[i]);
                printf ("\n");
    }
}

int main() {
        int n,i;
        printf ("Enter array size:\n");
        scanf("%d", &n);
        int *numarr = calloc(n, sizeof(int));
        if (numarr == NULL)
                return -1;
        gen_bit_array(numarr, n, n);
        return 0;
}

Output:

Enter array size:
2
00
01
10
11

Enter array size:
4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Clerisse Lucas · Answer 6 · 2017-10-26T12:58:59.443

0

No need for an algorithm, you could build a function,

Here is a process which could be a good idea if the array is of a fixed size :

Build a function which take your array
Create a local integrer for this function
Set the bits value of the integrer to the cells value of the array
Increment the integrer
Set the array values to match each bits of the integrer

All this process can be done using shifts (>> <<) and masks (& 255 for example).

edited Oct 26 '17 at 12:58

answered Oct 26 '17 at 12:56

Clerisse Lucas

43
10

It is of dynamic size however, I'll update my question to reflect that more clearly – Isaiah Oct 26 '17 at 12:58

C - iterate over array of 0s & 1s as if binary number

6 Answers6