2

I have a constant called A defined in a header file; it is always an even number.

I would like to declare an array B in the same header file whose length depends on the value of A.

For example;

If A is 32, I would like the array size to be 4, (2,4,8,16 being the elements. All powers of 2 till A/2).

If A is 48, I would like the array size to be 5, (2,4,8,16,24 being the elements. All powers of 2 till A/2 and the last element being A/2).

What is an elegant way to calculate the array size of B given a value of A using the above logic?

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
PyariBilli
  • 501
  • 1
  • 7
  • 17
  • Why do you have to declare the array statically. This sounds like something that requires calculation and dynamic allocation. – eyalm Nov 09 '14 at 05:52
  • i want the array declared in the header becuse i will use it across multiple c files. – PyariBilli Nov 09 '14 at 05:54
  • You can define it in one module and export it using 'extern' – Omer Eldan Nov 09 '14 at 06:28
  • @OmerEldan Can you give an example and post it as an answer please – PyariBilli Nov 09 '14 at 06:30
  • The size of the array needs to be floor(log2(A-1)), I think. Expressing that as a compile-time computable constant value is not trivial. – Jonathan Leffler Nov 09 '14 at 06:33
  • @JonathanLeffler is there a trivial bound which I can use such that floor(log2(A-1)) is always less than that. – PyariBilli Nov 09 '14 at 06:35
  • Is there an upper bound on A? If A is 256 or less, then floor(log2(A-1)) is 7, I think. – Jonathan Leffler Nov 09 '14 at 06:36
  • @JonathanLeffler I was thinking more on the lines of a easily defined bound depending on A. But yeah I could use a hard bound for all A. For now max A is 512 but may change. – PyariBilli Nov 09 '14 at 06:39
  • @JonathanLeffler is there an inbuilt function in C to calculate log base 2 – PyariBilli Nov 09 '14 at 06:41
  • OK; your array isn't exactly going to be huge (63) if your value of A goes up to 18446744073709551615 (maximum size of an unsigned 64-bit integer), so you can put a bound of 63 on your array. More realistically, you could probably choose 16 and have oodles of room for growth. – Jonathan Leffler Nov 09 '14 at 06:41
  • Only for floating point, which is why it is non-trivial — you'd use `log()` from ``. You also can't use functions for initializers in variables at file scope or static in a function; only for automatic variables. You might do worse than `A <= 4 ? 1 : A <= 8 ? 2 : A <= 16 ? 3 : A <= 32 ? 4 : A <= 64 ? 5 : …`. – Jonathan Leffler Nov 09 '14 at 06:44

3 Answers3

3

You need to use a #define for A, but given that you do that, you can manage using some scheme like this:

#define A 384

#define B_SIZE (A <= 16 ? 3 : A <= 32 ? 4 : A <= 64 ? 5 : A <= 128 ? 6 : \
                A <= 256 ? 7 : A <= 512 ? 8 : A <= 1024 ? 9 : -1)

extern int B[B_SIZE];

The use of -1 as the tail value is not accidental; it ensures a compilation error because you can't have arrays with a negative size, so if A is too big, the code won't compile. You could use the same trick to rule out sizes that are too small, too.

In the code that defines and initializes the array, you use:

int B[B_SIZE] =
{
    2, 4,
#if A > 16
    8,
#endif
#if A > 32
    16,
#endif
#if A > 64
    32,
#endif
#if A > 128
    64,
#endif
#if A > 256
    128,
#endif
#if A > 512
    256,
#endif
    A/2
};

This isn't elegant, but I'm not sure there's a neater way to do it. This uses B_SIZE explicitly again to ensure a compilation error again if the value of A is out of bounds. You could otherwise just leave the B_SIZE out of the array specification.

You could easily write a shell (Awk, Perl, Python, …) script to generate the code up to a given size.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
2

Maybe I am missing something. Why don't you simply define the array as:

int array[] = {
   2,4,8,16
#if A == 48
   ,24
#endif
};

#define DIM_OF_ARRAY (sizeof(array)/sizeof(array[0]))
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Marian
  • 7,402
  • 2
  • 22
  • 34
  • 1
    But note that this should be defined this way in a C source file. The header should contain only `int array[];`. – Jens Nov 09 '14 at 10:45
1

If we can limit A to always be a power of two, then this is related to another problem: "How do you compute the number of value bits in an integer type at compile time?" This problem was solved beautifully by Hallvard B Furuseth more than a decade ago. See: https://stackoverflow.com/a/4589384/3478852

Using Hallvard's solution, we can compute the array size as follows:

#include <stdio.h>

/* Number of bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 2040 */
#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))

#define A 1073741824

int B[IMAX_BITS(A/2-1)];

int main (void)
{
  printf ("%d\n", (int)(sizeof B / sizeof B[0]));
  return 0;
}

Note:

  • The number A must be a power of two.
  • The code uses the simpler version of the macro that is only accurate up to 2039 bits. There is another version in the article for ridiculously large numbers.
Community
  • 1
  • 1
Nisse Engström
  • 4,738
  • 23
  • 27
  • 42