Наиболее эффективный способ найти пересечение между двумя наборами чисел, закодированных с помощью побитовых операций - PullRequest
Новая
       3

Наиболее эффективный способ найти пересечение между двумя наборами чисел, закодированных с помощью побитовых операций

0 голосов
/ 05 февраля 2020

Учитывая два набора чисел, закодированных с помощью побитовых операций (используя 6 битов для числа): 

 a = {12,20,21,24,31}
 b = {13,18,24,28,35}

 Intersection -> a ∩ b = {24}

 unsigned int a = 0;
 a |= (12 | 20 << 6 | 21 << 12 | 24 << 18 | 31 << 24);

 unsigned int b = 0;
 b |= (13 | 18 << 6 | 24 << 12 | 28 << 18 | 35 << 24);

Какой самый быстрый способ выяснить, если между наборами есть хотя бы одно общее число ?

Это только пример, но вы можете иметь общие номера в любой позиции.

Ответы [ 4 ]

3 голосов
/ 05 февраля 2020 
#include <stdint.h>
#include <limits.h>


typedef unsigned int SetType;
#define FieldWidth 6 // Number of bits per field.

#define NumberOfFields (sizeof(SetType) * CHAR_BIT / FieldWidth)


//  Return non-zero iff some element is in both a and b.
int IsIntersectionNonEmpty(SetType a, SetType b)
{
    // Create masks with a bit set for each element an input set.
    uint64_t A = 0, B = 0;
    for (int i = 0; i < NumberOfFields; ++i)
    {
        A |= UINT64_C(1) << (a >> i*6 & 0x3f);
        B |= UINT64_C(1) << (b >> i*6 & 0x3f);
        /*  ">> i*6" moves field i to the low bits.
            "& 0x3f" isolates that six-bit field.
            "UINT64_C(1) << …" generates a 1 bit in that position.
        */
    }

    /* Bitwise AND A and B to see if they have a bit in common, then
       convert that to 1 or 0.
    */
    return !! (A & B);
}
1 голос
/ 05 февраля 2020

Может быть, не самый быстрый, но я бы XOR a с b, и посмотреть, есть ли в результате какой-либо шаблон из шести битов все нули в любой из ваших 5 позиций. Затем сдвиньте один из них на 6 бит и повторите при необходимости еще 4 раза.

0 голосов
/ 06 февраля 2020

Ну, спасибо всем, но спасибо парню, который разместил код EL, я не знаю, почему он снял его. Здесь мы go, так быстро, как свет: 

 #define EL(x) (UINT64_C(1) << (x)) 
 unsigned int a = 0;
 a |= (12 | 20 << 6 | 21 << 12 | 24 << 18 | 31 << 24);

 unsigned int b = 0;
 b |= (13 | 18 << 6 | 24 << 12 | 28 << 18 | 35 << 24);

 unsigned int aa = EL(a & 0x00000003F) | EL((a & 0x000000FC0) >> 6) | EL((a & 0x3F000) >> 12) | EL((a & 0xFC0000) >> 18) | EL((a & 0x3F000000) >> 24);
 unsigned int bb = EL(b & 0x00000003F) | EL((b & 0x000000FC0) >> 6) | EL((b & 0x3F000) >> 12) | EL((b & 0xFC0000) >> 18) | EL((b & 0x3F000000) >> 24);

 anb = !! (aa & bb);  // intersection
0 голосов
/ 05 февраля 2020

Вот несколько более быстрая версия моего решения выше; вместо смещения влево и вправо, просто поверните: 

int leftRotate(unsigned int n, unsigned int d) 
{ 
    return (n << d)|(n >> (32 - d)); 
} 

//  Return non-zero iff some element is in both a and b.
int IsIntersectionNonEmpty(unsigned int a, unsigned int b)
{
    for (int i = 0; i < 5; i++) {
        unsigned int matches = leftRotate(a, i*6) ^ b;
        for (int j = 0; j < 5; j++) {
            unsigned int testval = 0x3f << j*6;
            if (matches & testval == testval)
                return 1; // success
        }
    }
    return 0;
}

5 инструкций во внешней l oop, 3 во внутренней * 5, итого 20, 5 циклов, около 100 инструкций - но как только он находит совпадение, он возвращается. Так что, если есть частые совпадения, это, вероятно, будет быстрее, чем версия @ eri c -postpischil, но без совпадений это будет медленнее. С другой стороны, его решение, вероятно, автоматически векторизуемо с помощью умного компилятора.

...