Этот метод использует менее 2 проходов (но изменяет входной массив)
#include <stdio.h>
unsigned array[] = { 0,1,2,3,4,5,6,7,8,16,17 };
#define COUNTOF(a) (sizeof(a)/sizeof(a)[0])
void swap(unsigned *a, unsigned *b)
{
unsigned tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
int main(void)
{
unsigned idx,bot,totmask,dupmask;
/* First pass: shift all elements that introduce new bits into the found[] array.
** totmask is a mask of bits that occur once or more
** dupmask is a mask of bits that occur twice or more
*/
totmask=dupmask=0;
for (idx=bot=0; idx < COUNTOF(array); idx++) {
dupmask |= array[idx] & totmask;
if (array[idx] & ~totmask) goto add;
continue;
add:
totmask |= array[idx];
if (bot != idx) swap(array+bot,array+idx);
bot++;
}
fprintf(stderr, "Bot=%u, totmask=%u, dupmask=%u\n", bot, totmask, dupmask );
/* Second pass: reduce list of candidates by checking if
** they consist of *only* duplicate bits */
for (idx=bot; idx-- > 0 ; ) {
if ((array[idx] & dupmask) == array[idx]) goto del;
continue;
del:
if (--bot != idx) swap(array+bot,array+idx);
}
fprintf(stdout, "Results[%u]:\n", bot );
for (idx=0; idx < bot; idx++) {
fprintf(stdout, "[%u]: %x\n" ,idx, array[idx] );
}
return 0;
}
ОБНОВЛЕНИЕ 2011-11-28
Другая версия, которая не изменяет исходный массив. (Временные) результаты хранятся в отдельном массиве.
#include <stdio.h>
#include <limits.h>
#include <assert.h>
unsigned array[] = { 0,1,2,3,4,5,6,7,8,16,17,32,33,64,96,128,130 };
#define COUNTOF(a) (sizeof(a)/sizeof(a)[0])
void swap(unsigned *a, unsigned *b)
{
unsigned tmp;
tmp = *a, *a = *b, *b = tmp;
}
int main(void)
{
unsigned idx,nfound,totmask,dupmask;
unsigned found[sizeof array[0] *CHAR_BIT ];
/* First pass: save all elements that introduce new bits to the left
** totmask is a mask of bits that occur once or more
** dupmask is a mask of bits that occur twice or more
*/
totmask=dupmask=0;
for (idx=nfound=0; idx < COUNTOF(array); idx++) {
dupmask |= array[idx] & totmask;
if (array[idx] & ~totmask) goto add;
continue;
add:
totmask |= array[idx];
found[nfound++] = array[idx];
assert(nfound <= COUNTOF(found) );
}
fprintf(stderr, "Bot=%u, totmask=%u, dupmask=%u\n", nfound, totmask, dupmask );
/* Second pass: reduce list of candidates by checking if
** they consist of *only* duplicate bits */
for (idx=nfound; idx-- > 0 ; ) {
if ((found[idx] & dupmask) == found[idx]) goto del;
continue;
del:
if (--nfound != idx) swap(found+nfound,found+idx);
}
fprintf(stdout, "Results[%u]:\n", nfound );
for (idx=0; idx < nfound; idx++) {
fprintf(stdout, "[%u]: %x\n" ,idx, found[idx] );
}
return 0;
}