Anonymous user
Prime triangle: Difference between revisions
→{{header|C}}: add second method
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: document the why the 'splice' sometimes needed) |
(→{{header|C}}: add second method) |
||
Line 235:
Elapsed time: 0.572986 seconds
</pre>
=== Use bit patterns ===
Number combinations are all stored in bit positions here. The <code>bpos()</code> functions returns the position index of the least significant bit in an integer. This code gains some speed, at the cost of total loss of readability. On the plus side, it has some bit manipulation tricks that may be interesting to some.
<lang C>#include <stdio.h>
#include <stdint.h>
#define GCC_ASM // use GCC's asm for i386. If it does not work, #undef it to use alternative func
typedef uint32_t uint;
typedef uint64_t ulong;
#define MASK 0xa08228828228a2bULL
#ifdef GCC_ASM
static inline uint
bpos(uint x)
{
uint b;
asm("bsf %0, %0" : "=r" (b): "0" (x));
return b;
}
#else
static inline uint
bpos(uint x)
{
static const uint bruijin[32] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
return bruijin[((uint)((x & -x) * 0x077CB531U)) >> 27];
}
#endif // GCC_ASM
int count(uint n, const uint s, uint avail)
{
int cnt = 0;
avail ^= s;
if (--n)
for (uint b = (uint)(MASK>>bpos(s)) & avail; b; b &= b-1)
cnt += count(n, b&-b, avail);
else
return (MASK & s) != 0;
return cnt;
}
int disp(uint n, const uint s, uint avail, int maxn, uint *seq)
{
seq[n--] = s;
if (!n) {
if ((MASK & s)) {
for (int i = 0; i < maxn; i++)
printf(" %d", bpos(seq[i]) + 1);
putchar('\n');
return 1;
}
} else {
for (uint b = (uint)(MASK>>bpos(s)) & (avail ^= s); b; b &= b-1)
if (disp(n, b&-b, avail, maxn, seq))
return 1;
}
return 0;
}
int chain(uint n, int count_only)
{
const uint top = 1U<<(n - 1);
const uint avail = 2*top - 2;
if (count_only)
return count(n - 1, top, avail);
uint seq[32];
seq[0] = 1;
disp(n - 1, top, avail, n, seq);
return 0;
}
int main(void)
{
for (int n = 2; n < 21; n++)
chain(n, 0);
putchar('\n');
for (int n = 2; n < 21; n++)
printf("%d ", chain(n, 1));
putchar('\n');
return 0;
}</lang>
{{out}}
<pre> 1 2
1 2 3
1 2 3 4
1 4 3 2 5
1 4 3 2 5 6
1 6 5 2 3 4 7
1 4 7 6 5 2 3 8
1 4 7 6 5 8 3 2 9
1 6 7 4 9 8 5 2 3 10
1 10 9 8 5 6 7 4 3 2 11
1 10 9 8 11 6 7 4 3 2 5 12
1 12 11 8 9 10 7 6 5 2 3 4 13
1 12 11 8 9 10 13 4 7 6 5 2 3 14
1 12 11 8 5 14 9 10 13 6 7 4 3 2 15
1 12 11 8 15 14 9 10 13 4 7 6 5 2 3 16
1 10 13 16 15 14 9 8 11 12 5 6 7 4 3 2 17
1 12 17 14 15 16 13 10 9 8 11 6 7 4 3 2 5 18
1 18 13 16 15 14 17 12 11 8 9 10 7 6 5 2 3 4 19
1 18 19 10 13 16 15 14 17 12 11 8 9 4 7 6 5 2 3 20
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162</pre>
=={{header|C++}}==
| |||