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 .

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

Best regards .