271 lines
6.9 KiB
C
271 lines
6.9 KiB
C
|
|
#include <stdio.h>
|
|
#include <assert.h>
|
|
|
|
#ifdef ZDEBUG
|
|
#define zprintf(fmt, ...) printf(fmt, ## __VA_ARGS__);
|
|
#else
|
|
#define zprintf(...) ;
|
|
#endif
|
|
|
|
int a = 17;
|
|
|
|
// 0 1 2 3 4 5 6 7 8 9
|
|
int b[10] = {10, 11, 11, 14, 14, 19, 20, 23, 26, 29};
|
|
|
|
int c[20] = {
|
|
// 0 1 2 3 4 5 6 7 8 9
|
|
15, 17, 19, 21, 22, 25, 26, 26, 27, 32,
|
|
|
|
// 10 11 12 13 14 15 16 17 18 19
|
|
33, 33, 36, 39, 42, 44, 48, 49, 49, 49
|
|
};
|
|
|
|
// [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9]
|
|
// 10 11 11 14 14 19 20 23 26 29
|
|
// --------------------------------------------------
|
|
// [ 0] 15 | 5 4 4 1 1 12 11 8 5 2
|
|
|
|
// [ 1] 17 | 17 16 16 17 17 0 1 0 1 0
|
|
|
|
// [ 2] 19 | 17 16 16 17 17 (0) 3 0 1 2
|
|
|
|
// [ 3] 21 | 21 20 20 17 17 4 (1) 0 5 0
|
|
|
|
// [ 4] 22 | 20 20 20 16 16 4 2 0 4 2
|
|
|
|
// [ 5] 25 | 17 16 16 17 17 8 9 8 1 0
|
|
|
|
// [ 6] 26 | 16 16 16 16 16 8 10 8 0 2
|
|
|
|
// [ 7] 26 | 16 16 16 16 16 8 10 8 0 2
|
|
|
|
// [ 8] 27 |(17) (16) (16) 17 17 8 11 8 ( 1) 2
|
|
|
|
// [ 9] 32 | 32 32 32 32 32 32 32 32 32 32
|
|
|
|
// [10] 33 | 33 32 32 33 33 32 33 32 33 32
|
|
|
|
// [11] 33 | 33 32 32 33 33 32 33 32 33 32
|
|
|
|
// [12] 36 | 36 36 36 32 32 36 32 32 36 32
|
|
|
|
// [13] 39 | 37 36 36 33 33 36 35 32 37 34
|
|
|
|
// [14] 42 | 32 32 32 32 32 40 42 40 32 34
|
|
|
|
// [15] 44 | 36 36 36 32 32 44 40 40 36 32
|
|
|
|
// [16] 48 | 48 48 48 48 48 32 32 32 32 32
|
|
|
|
// [17] 49 | 49 48 48 49 49 32 33 32 33 32
|
|
|
|
// [18] 49 | 49 48 48 49 49 32 33 32 33 32
|
|
|
|
// [19] 49 | 49 48 48 49 49 32 33 32 33 32
|
|
|
|
int binary(
|
|
int mask,
|
|
int *array,
|
|
int i, int n)
|
|
{
|
|
while (n > 1)
|
|
{
|
|
int m = n / 2;
|
|
|
|
if (array[i + m] & mask)
|
|
n = m;
|
|
else
|
|
i += m, n = n - m;
|
|
}
|
|
|
|
return (array[i] & mask) ? i : i + 1;
|
|
}
|
|
|
|
void quadrant_search(
|
|
int mask,
|
|
int bi, int bn,
|
|
int ci, int cn,
|
|
int calldepth)
|
|
{
|
|
zprintf("%*s" "quadrant_search():" "\n", calldepth++, "");
|
|
|
|
zprintf("%*s" "mask = 0b%05b" "\n", calldepth, "", mask);
|
|
|
|
zprintf("%*s" "bi = %i" "\n", calldepth, "", bi);
|
|
zprintf("%*s" "bn = %i" "\n", calldepth, "", bn);
|
|
|
|
zprintf("%*s" "ci = %i" "\n", calldepth, "", ci);
|
|
zprintf("%*s" "cn = %i" "\n", calldepth, "", cn);
|
|
|
|
if (mask)
|
|
{
|
|
int bsplit = binary(mask, b + bi, 0, bn);
|
|
int csplit = binary(mask, c + ci, 0, cn);
|
|
|
|
zprintf("%*s" "bsplit = %i" "\n", calldepth, "", bsplit);
|
|
zprintf("%*s" "csplit = %i" "\n", calldepth, "", csplit);
|
|
|
|
assert((bsplit == bn) || (b[bi + bsplit] & mask));
|
|
assert((csplit == cn) || (c[ci + csplit] & mask));
|
|
|
|
// 0 ... (bsplit - 1) | bsplit ... (an - 1)
|
|
// --------------------- -------------------
|
|
// 0 | | |
|
|
// ... | first quadrant. | second quadrant |
|
|
// (csplit - 1) | | |
|
|
// --- ---------------------- -------------------
|
|
// csplit | | |
|
|
// ... | third quadrant | fourth quadrant |
|
|
// (cn - 1) | | |
|
|
// --- | | |
|
|
// ---------------------- -------------------
|
|
|
|
if (mask & a)
|
|
{
|
|
zprintf("%*s" "one case" "\n", calldepth, "");
|
|
|
|
// third quadrant
|
|
if (0 < bsplit && csplit < cn)
|
|
{
|
|
zprintf("%*s" "entering third quadrant." "\n", calldepth, "");
|
|
|
|
quadrant_search(
|
|
mask >> 1,
|
|
bi, bsplit,
|
|
ci + csplit, cn - csplit,
|
|
calldepth);
|
|
}
|
|
else
|
|
{
|
|
zprintf("%*s" "empty third quadrant." "\n", calldepth, "");
|
|
}
|
|
|
|
// fourth quadrant
|
|
if (bsplit < bn && csplit < cn)
|
|
{
|
|
zprintf("%*s" "entering fourth quadrant." "\n", calldepth, "");
|
|
|
|
quadrant_search(
|
|
mask >> 1,
|
|
bi + bsplit, bn - bsplit,
|
|
ci + csplit, cn - csplit,
|
|
calldepth);
|
|
}
|
|
else
|
|
{
|
|
zprintf("%*s" "empty fourth quadrant." "\n", calldepth, "");
|
|
}
|
|
}
|
|
else
|
|
{
|
|
zprintf("%*s" "zero case" "\n", calldepth, "");
|
|
|
|
// first quadrant
|
|
if (0 < bsplit && 0 < csplit)
|
|
{
|
|
zprintf("%*s" "entering first quadrant." "\n", calldepth, "");
|
|
|
|
quadrant_search(
|
|
mask >> 1,
|
|
bi, bsplit,
|
|
ci, csplit,
|
|
calldepth);
|
|
}
|
|
else
|
|
{
|
|
zprintf("%*s" "empty first quadrant." "\n", calldepth, "");
|
|
}
|
|
|
|
// fourth quadrant
|
|
if (bsplit < bn && csplit < cn)
|
|
{
|
|
zprintf("%*s" "entering fourth quadrant." "\n", calldepth, "");
|
|
|
|
quadrant_search(
|
|
mask >> 1,
|
|
bi + bsplit, bn - bsplit,
|
|
ci + csplit, cn - csplit,
|
|
calldepth);
|
|
}
|
|
else
|
|
{
|
|
zprintf("%*s" "empty fourth quadrant." "\n", calldepth, "");
|
|
}
|
|
}
|
|
}
|
|
else for (int i = 0; i < bn; i++)
|
|
{
|
|
for (int j = 0; j < cn; j++)
|
|
{
|
|
assert((a | b[bi + i]) == c[ci + j]);
|
|
|
|
printf("%2i (0b%05b) | %2i [%2i] "
|
|
"(0b%05b) == %2i [%2i] (0b%05b)" "\n",
|
|
a, a,
|
|
b[bi + i], bi + i, b[bi + i],
|
|
c[ci + j], ci + j, c[ci + j]);
|
|
}
|
|
}
|
|
|
|
calldepth--;
|
|
}
|
|
|
|
void brute_force_search(int bn, int cn)
|
|
{
|
|
for (int bi = 0; bi < bn; bi++)
|
|
{
|
|
for (int ci = 0; ci < cn; ci++)
|
|
{
|
|
if ((a | b[bi]) == c[ci])
|
|
{
|
|
printf("%2i (0b%05b) | %2i [%2i] "
|
|
"(0b%05b) == %2i [%2i] (0b%05b)" "\n",
|
|
a, a,
|
|
b[bi], bi, b[bi],
|
|
c[ci], ci, c[ci]);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int main()
|
|
{
|
|
puts("divide-and-conquer:");
|
|
|
|
quadrant_search(32, 0, 10, 0, 20, 0);
|
|
|
|
puts("");
|
|
|
|
puts("brute-force:");
|
|
brute_force_search(10, 20);
|
|
|
|
return 0;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|