Fill array with binary numbers

Question

First of all this is not homework!

My question is from the book: Algorithms in C++ third edition by Robert Sedgewick.

There is given an array of size n by 2^n (two dimensional) and we should fill it with binary numbers of bits size exactly n. For example for n=5 the result will be:

00001
00010
00011
00100
00101
00110
00111    

And so on. We should put this sequence of bits into arrays.

Answer 1

I do not know much C/C++, but a naïve, language-agnostic approach would be to simply find a formula for A[i, j], where i \in [0, 2^n - 1] and j \in [0, n-1].

In words, A[i, j] contains the jth binary digit of i, counting from the most significant bit.

In formulae, A[i, j] = (i AND 2^(n-1-j) ) SHR (n-1-j)

where AND is the binary bitwise and operator, and SHR is the binary "shift bits right" operator. a^b means (of course) "a raised to the power of b".

Ugly Proof-Of-Concept Delphi Code:

var
  i: Integer;
  twoton: integer;
  j: Integer;
begin
  twoton := round(IntPower(2, n));
  SetLength(A, twoton, n);
  for i := 0 to twoton - 1 do
    for j := 0 to n - 1 do
      A[i, j] := (i and round(IntPower(2, n-1-j))) shr (n-1-j);

This works perfectly, but I am quite sure there are faster ways... At least one could store the powers of 2 in an array and use POWEROF2[k] rather than round(IntPower(2, k)), but - of course - this depends on your language. After all, IntPower is a Delphi function.

How this works

Say that we have the number 23, or, in binary 10111. Now we want the third binary digit. Then we want to AND the number 10111 with the number 00100, to obtain 00100 if the sought digit is one, and 00000 otherwise. Notice that 00100, the number we AND with, is simply 2^3 in decimal; hence all powers-of-2. Now we have the number 00N00, where N is the sought digit, in this example 1: 00100. We now shift the bits of this number 3 steps to the right (the SHR operation), to obtain 00001 = 1, and - voilà! - we have gotten our digit!

A Smarter Approach

I do not know how C stores arrays, but you could simply create a 2^N-dimensional vector A of unsigned integers (8-bit, 16-bit, or 32-bit, preferably), namely the numbers 0, 1, 2, ..., 2^N - 1, and then argue that this actually is a two-dimensional matrix. Indeed, if we introduce the notation UNSINGED_INTEGER[k] as the kth bit of UNSIGNED_INTEGER, then A[i][k] is more or less the matrix you wanted...

Answer 2

So basically, you need an array that starts at zero, and goes up to 2^n?
Psuedo-C:

bool[][] Fill(int n) {
   max = Pow(2, n);
   array = new bool[max, n];

   for i from 0 to max - 1
      for j from 0 to n - 1
         array[i][n - j - 1] = ((i >> j) & 1) == 1;
   return array;
}

The only problem I can see with that is that it capped at n = 32, but that will already take enormous amounts of memory so that really is a non-issue.
Note that you could as well make it a one dimensional number and fill it with numbers from 0 to 2^n, and the A[i][j]th element will actually be retrieved using (A[i]>>j) & 1.

Answer 3

This is a very rudimentary problem, and I will demonstrate with this Java snippet:

public class Bin {                                                  // prints:   
   static String zero(int L) {                                      // 0000
      return (L <= 0 ? "" : String.format("%0" + L + "d", 0));      // 0001
   }                                                                // 0010
   static String zeroPad(String s, int L) {                         // 0011
      return zero(L - s.length()) + s;                              // 0100
   }                                                                // 0101
   public static void main(String[] args) {                         // 0110
      final int N = 4;                                              // 0111
      for (int i = 0; i < (1 << N); i++) {                          // 1000
         System.out.println(zeroPad(Integer.toBinaryString(i), N)); // 1001
      }                                                             // 1010
   }                                                                // 1011
}                                                                   // 1100
                                                                    // 1101
                                                                    // 1110
                                                                    // 1111

I will leave it to you to figure out how to implement toBinaryString and how to populate int[][] with the bits.

Answer 4

Each number is one more than the last in the binary number system.

To increment (add one) in binary

• start at the right end of the number
• turn all trailing ones, if any, into zeroes
• turn the last 0 into a 1
• if there isn't a 0 in the string, you've gone too far.

Note that the << operator multiplies the left operand by two to the power of the right operand. The number 1l is simply 1 expressed as a long, which is 64 bits on a 64-bit system.

template< size_t n > // template detects size of array. Strictly optional.
void ascending_binary_fill( bool (&arr)[ 1l << n ][ n ] ) {
    std::fill( arr[0], arr[0] + n, 0 ); // first # is 0
    for ( size_t pred = 0; pred < 1l << n; ++ pred ) {
        int bit = n; // pred = index of preceding number; bit = bit index
        while ( arr[ pred ][ -- bit ] ) { // trailing 1's in preceding #
            arr[ pred+1 ][ bit ] = 0; // ... are trailing 0's in current #
        }
        arr[ pred+1 ][ bit ] = 1;
        std::copy( arr[ pred ], arr[ pred ] + bit, arr[ pred+1 ] );
    }
}