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 .