Thread: Dynamic array - size calculation

  1. #1
    Registered User
    Join Date
    Jan 2021
    Posts
    2

    Question Dynamic array - size calculation

    Greetings fella's!

    I have been trying to tackle this programming exercise:

    Given a number 'n', calculate and store the results of doing 3 bitwise operations: '&', '|','^' for each combination of (a,b) given that:
    n : 2 <= n <= 1000
    a : 1 <= a <= n
    b : a + 1 <= b <= n.

    I am supposed to save all results in a table for further processing (which is not relevant for this question).

    I came up with this function (just the problematic part):
    Code:
    void calculate_bitwise_combinations(int n)
    {
           int bitwise_results[/*how do i calculate the size?*/];
           for(int a = 1; a <= n; a++) {
                  for(int b = a+1, *it = &bitwise_results[a-1]; b <= n; b++) {
                                    *it++ = (a&b);
                                    *it++ = (a|b);
                                    *it++ = (a^b);
                            } 
                    }
    /// further processing here
    }
    (I am using a pointer-iterator that updates automatically on each sub-loop, just for convenience).

    The issue I've run across is to calculate the size of the dynamic array, I've tried 3*(n*(n-1)) and 3*(n*n) but as 'n' gets larger, it either overshoots or undershoots the size making it unnecessarily large or too short to store all possible results.

    How would i (or you) go about calculating the size of the table fast and cheap?

    (this is not for school or work, just for fun).

    Thanks you in advance and have a good day.

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,066
    'a' must only go up to n - 1 since 'b' must start at 'a + 1' but not go over 'n'. When 'a' is 1, there will be n - 1 'b's, when 'a' is n - 1 there will be 1 'b'. So the number of triples (n-1)+(n-2)+...+1, which is n * (n - 1) / 2.
    Code:
    void calculate_bitwise_combinations(int n)
    {
        int *results = malloc(3 * n * (n - 1) / 2 * sizeof *results);
        if (!results) { perror("malloc"); exit(EXIT_FAILURE); }
        int *it = results;
        for (int a = 1; a < n; a++) {
            for (int b = a + 1; b <= n; b++) {
                *it++ = a & b;
                *it++ = a | b;
                *it++ = a ^ b;
            } 
        }
     
        // ...
       
        free(results);
    }
    Philosophy is a battle against the bewitchment of our intelligence by means of language. - Wittgenstein

  3. #3
    Registered User
    Join Date
    Jan 2021
    Posts
    2
    Quote Originally Posted by john.c View Post
    'a' must only go up to n - 1 since 'b' must start at 'a + 1' but not go over 'n'. When 'a' is 1, there will be n - 1 'b's, when 'a' is n - 1 there will be 1 'b'. So the number of triples (n-1)+(n-2)+...+1, which is n * (n - 1) / 2.
    Code:
    void calculate_bitwise_combinations(int n)
    {
        int *results = malloc(3 * n * (n - 1) / 2 * sizeof *results);
        if (!results) { perror("malloc"); exit(EXIT_FAILURE); }
        int *it = results;
        for (int a = 1; a < n; a++) {
            for (int b = a + 1; b <= n; b++) {
                *it++ = a & b;
                *it++ = a | b;
                *it++ = a ^ b;
            } 
        }
     
        // ...
       
        free(results);
    }
    Thank you, I actually came up with this while tinkering with it:
    Code:
    int bitwise_results(3*(n-1)*(n>>1)];
    Yours though is more portable and has the plus to be able to return the buffer if needed.

    I tried with calloc instead of malloc, since calloc is designed for allocating arrays:
    Code:
    int* calculate_bitwise_combinations(int n)
    {
        int* results = calloc(3*(n-1)*(n>>1), sizeof *results);
        if (!results) { perror("calloc"); exit(EXIT_FAILURE); }
        int *it = results;
        for (int a = 1; a < n; a++) {
            for (int b = a + 1; b <= n; b++) {
                *it++ = a & b;
                *it++ = a | b;
                *it++ = a ^ b;
            }
        }
        return results;
    }
    I was curious as to how both options would perform and ran both the malloc and calloc version in compiler explorer on gcc(trunk) x86_64 and clang(11.0.1) x86_64 with -O3 to find out, the results were:

    gcc(trunk)

    • Malloc = 57 lines of assembly
    • Calloc = 55 lines of assembly (57 with a division instead of a bitshift)


    clang(11.0.1):
    • Malloc = 87 lines of assembly
    • Calloc = 85 lines of assembly (87 with a division instead of a bitshift)


    -O2 gave the same result; no optimization was painfully verbose, almost 30% more lines for each (+25 g.o.t).

    Both malloc and calloc performed the same, which is suprising since calloc still needs to initialize memory to 0 and malloc technically doesn't.
    Also looks like the right shift division trick is still slightly more efficient than a division by a power of 2, by 2 instructions at least .

    Anyhow thank you for answering my first post, i hope my post-analysis was valuable to you as yours was to me.

    Best regards .


  4. #4
    Registered User
    Join Date
    Dec 2017
    Posts
    1,066
    This is not correct if n is odd:
    Code:
    3*(n-1)*(n>>1)   // or (n/2) instead of n>>1
    You need to multiply n*(n-1) first to ensure that the result is even before dividing by 2.
    Code:
    Suppose n is 5:
      (5 - 1) * 5 / 2 = 20 / 2 = 10, the correct answer
      (5 - 1) * (5 / 2) = 4 * 2 = 8, oops!
    calloc is not "designed for allocating arrays". It simply zeroes the allocated bytes. You may as well use malloc since you don't need them zeroed.
    Philosophy is a battle against the bewitchment of our intelligence by means of language. - Wittgenstein

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamic Array Size
    By iyilikpenisi in forum C Programming
    Replies: 2
    Last Post: 09-16-2016, 02:15 PM
  2. Dynamic Array - Size
    By vijay s in forum C Programming
    Replies: 2
    Last Post: 01-17-2012, 11:11 PM
  3. How to get the size of an dynamic array?
    By sept in forum C++ Programming
    Replies: 7
    Last Post: 09-18-2007, 02:26 PM
  4. Dynamic Array Size?
    By Junior89 in forum C++ Programming
    Replies: 4
    Last Post: 04-04-2007, 11:31 PM
  5. size of dynamic array
    By tommy_gunn in forum C Programming
    Replies: 3
    Last Post: 12-30-2004, 08:01 PM

Tags for this Thread