Fill an array with binary numbers
First of all, this is not homework!
My question is from the book: Algorithms in C ++ 3rd Edition by Robert Sedgewick.
Here we have given an array of size n by 2 ^ n (two-dimensional), and we must fill it with binary numbers of bits of exactly n size. For example, for n = 5, the result is:
00001
00010
00011
00100
00101
00110
00111
Etc. We have to put this sequence of bits into arrays.
a source to share
This is a very rudimentary problem and I'll 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'll leave it to you to figure out how to implement toBinaryString
and how to fill with int[][]
bits.
a source to share
I don't know much C / C ++, but a naive, agnostic approach would be to just 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 j-th binary digit i, counted from the most significant bit.
In formulas 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 right shift operator. a ^ b means (of course) "a raised to degree 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 great, but I'm sure there are faster ways ... At least one could store in a power array of 2 and use POWEROF2 [k] rather than round (IntPower (2, k)), but - Of course, it depends on your language. After all, IntPower is a Delphi feature.
How it works
Let's say we have number 23, or in binary 10111. Now we need the third binary digit. Then we want the AND number 10111 numbered 00100 to get 00100 if the desired digit is one, and 00000 otherwise. Note that 00100, the number we AND with, is just 2 ^ 3 in decimal; hence, all powers are 2. Now we have the number 00N00, where N is the desired digit, in this example 1: 00100. Now we shift the bits of this number 3 steps to the right (SHR operation) to get 00001 = 1 and - voilà! - we got our figure!
Smart approach
I don't know how C stores arrays, but you can just create a 2 ^ N-dimensional vector A of unsigned integers (preferably 8-bit, 16-bit, or 32-bit), namely the numbers 0, 1, 2, .. ., 2 ^ N - 1 and then claim to be actually a two-dimensional matrix. Indeed, if we introduce the notation UNSINGED_INTEGER [k] as the k-th bit of UNSIGNED_INTEGER, then A [i] [k] is more or less a necessary matrix ...
a source to share
Each number is greater than the last in binary.
To increase (add one) in binary
- start from the right end of the number
- turn all trailing ones, if any, to zeros
- turn the last 0 into 1
- If there is no 0 on the line, you have gone too far.
Note that the operator <<
multiplies the left operand by two by the power of the correct operand. The number is 1l
simply 1
expressed as 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 in preceding #
arr[ pred+1 ][ bit ] = 0; // ... are trailing 0 in current #
}
arr[ pred+1 ][ bit ] = 1;
std::copy( arr[ pred ], arr[ pred ] + bit, arr[ pred+1 ] );
}
}
a source to share
public static uint[][] FillUpCode(uint qValue, uint kValue)
{
var size = (ulong)Math.Pow(qValue, kValue);
var array = new uint[size][];
var workArray = new uint[kValue];
long position = kValue - 1;
ulong n = 0;
while (position > 0)
{
while (workArray[position] < qValue)
{
var tempArray = new uint[kValue];
Array.Copy(workArray, tempArray, kValue);
array[n++] = tempArray;
workArray[position]++;
}
while (position > 0)
{
workArray[position] = 0;
if (workArray[position - 1] < (qValue - 1))
{
workArray[position - 1]++;
position = kValue - 1;
break;
}
position--;
}
}
return array;
}
qValue - numeric base, string length kValue :) The code can be useful when you need to generate an array in different quantities.
a source to share
So basically, you want 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 see is that it is limited to n = 32, but this will already require huge amounts of memory, so it really isn't a problem.
Note that you can also make this a one-dimensional number and fill it with digits from 0 to 2 ^ n, and the element A [i] [j] th will actually be obtained using (A [i] → j) and 1.
a source to share
// My solution is based on that of Potatoswatter.
// use cols value where rows = 2^cols
// start here after setting cols
rows = pow(2.0, double(cols));
// memory allocation
bool **array = new bool*[rows];
for (int i = 0; i < rows; i++) {
array[i] = new bool[cols];
}
std::fill( array[0], array[0] + cols, 0 ); // maybe not needed
for (int i = 1; i < rows; i++) { // first row is zero, start at second
// starting at right ...
int j = lits - 1;
// turn the last zero into a one
if (array[i][j] == false) {
array[i][j] = true;
}
else {
// turn all trailing ones into zeros (prior to first zero)
while (array[i][j] == true) {
array[i][j] = false;
j--;
}
array[i][j] = true;
}
// copy this row to next row
if (i < (rows - 1)) {
std::copy(array[i], array[i] + lits, array[i+1]);
}
}
a source to share