Dynamic array - size calculation

Greetings fella's! :biggrin:

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. :cool:

'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);
}

---

Quote:

---

Originally Posted by john.c

'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 :p.

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

Best regards :cool:.

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.