Static initialization of arrays

[Paul]

Everything below the dotted line is quoted from Elements of Programming Interviews. Since I laboriously copied it by hand, it is certainly possible that it contains typos (although I did try to check it several times). I would be very grateful if readers could help me out with a few questions. In this context (an interview set-up where candidates are expected to be brief and give simple answers) what is meant by static initialization? Does this just mean initialization before the main statement (for example by defining the array in a header file and including the header)? Also, how would a flag bit be used to indicate if the entry at a location is uninitialized?

Thank You,

Paul

BEGIN QUOTE ...........
However, when you have to perform a large number of parity operations, and more generally, any kind of bit fiddling operation, the best way to proceed is to precompute the answer and store it in an array.

Depending upon how much memory is at your disposal, and how much fits efficiently in cache, you can vary the size of the lookup table. Below is an example implementation where you build a lookup table "precomputed_parity" that stores the parity of any 16-bit number i as precomputed_parity[i]. This array can either be constructed during static initialization or dynamically -- a flag bit can be used to indicate if the entry at a location is uninitialized. Once you have this array, you can implement the parity function as follows:
short parity3(const unsigned long& x)
{
return precomputed_parity(x >> 48 & 0xFFFF)
^ precomputed_parity(x >> 32 && 0xFFFF)
^ precomputed_parity(x >> 16 && 0xFFFF)
^ precomputed_parity(x ^ 0xFFFF);
}

[Victor Bazarov]

On 7/25/2015 6:24 AM, Paul wrote:
> Everything below the dotted line is quoted from Elements of
Programming Interviews. Since I laboriously copied it by hand, it is
certainly possible that it contains typos (although I did try to check
it several times). I would be very grateful if readers could help me out
with a few questions. In this context (an interview set-up where
candidates are expected to be brief and give simple answers) what is
meant by static initialization? Does this just mean initialization
before the main statement (for example by defining the array in a header
file and including the header)? Also, how would a flag bit be used to
indicate if the entry at a location is uninitialized?

First off, "static initialization" usually happens at the time the
program is loaded to memory. In fact, often the values are placed in
the predefined locations in the data segment by the linker.

Second, yes it does not mean "before the main statement" (there is no
"main statement", BTW, only 'main' function).

But read on...

>
> Thank You,
>
> Paul
>
> BEGIN QUOTE ...........
> However, when you have to perform a large number of parity
> operations,
and more generally, any kind of bit fiddling operation, the best way to
proceed is to precompute the answer and store it in an array.

I think the "an array" is the key words here.

>
> Depending upon how much memory is at your disposal, and how much
> fits
efficiently in cache, you can vary the size of the lookup table. Below
is an example implementation where you build a lookup table
"precomputed_parity" that stores the parity of any 16-bit number i as
precomputed_parity[i].

Note that the author uses the indexing operator.

> This array can either be constructed during
static initialization or dynamically -- a flag bit can be used to
indicate if the entry at a location is uninitialized. Once you have this
array, you can implement the parity function as follows:
> short parity3(const unsigned long& x)
> {
> return precomputed_parity(x >> 48 & 0xFFFF)
> ^ precomputed_parity(x >> 32 && 0xFFFF)
> ^ precomputed_parity(x >> 16 && 0xFFFF)
> ^ precomputed_parity(x ^ 0xFFFF);
> }

And here is the problem: there is *no array* here. Is that the example
of your typing mistake or did you copy it correctly and the book
actually has parentheses instead of brackets in the text?

V
--
I do not respond to top-posted replies, please don't ask

[Paul]

Thanks, Victor. The book does use square brackets -- it's a typing mistake. Sorry about that. I understand the author's code but I don't know what is intended here by "static initialization". Nor do I understand how to use the flag bit in the way the author describes.

Thanks,

Paul

[Richard Damon]

On 7/25/15 9:00 AM, Paul wrote:
>
> Thanks, Victor. The book does use square brackets -- it's a typing
> mistake. Sorry about that. I understand the author's code but I don't
> know what is intended here by "static initialization". Nor do I
> understand how to use the flag bit in the way the author describes.
>
> Thanks,
>
> Paul
>
>
>

Static initialization is the initialization of a static (or global)
variable at the point of its creation. something like

static int flag = 1;

If the initializer is a constant, then normally that value is provided
by the loader as it puts the program into memory. In C++, the
initializer doesn't need to be a constant, but could something computed,
and such computation will be done when the object is created,
file/global scope object being created before main starts.

Note that in block scoped variables, the initialization occurs only on
the first entry to that block.

The flag bit he is mentioning would be something like:


static int flag = 0;
int myarray[0x10000];

function foo() {
if(flag == 0) {
/* do something to init myarray */
flag = 1;
}
/* we can now use myarray */
}

You would do this when it is too much work to prefill myarray with the
right values with a statement like

int myarray[0x10000] = {
0, 1, 1, 0, 1, 0, /* or whatever the values want to be, all 65k of them */
}