Какой самый быстрый способ подсчитать количество совпадающих цифр в базе 4? - PullRequest
Новая
       14

Какой самый быстрый способ подсчитать количество совпадающих цифр в базе 4?

4 голосов
/ 12 февраля 2012

С учетом двух целых чисел без знака, какой самый быстрый способ подсчитать количество совпадающих цифр в их базовом представлении 4?

пример 1:

A = 13 = (31) в базе4

B = 15 = (33) в базе 4

количество совпадающих цифр в базе 4 равно 1.

пример 2:

A= 163 = (223) в базе 4

B = 131 = (203) в базе 4

количество совпадающих цифр в базе 4 равно 2.

Первыйшаг, который я предполагаю, чтобы вычислить побитовое XOR двух целых чисел, тогда мы должны посчитать количество пар 00?Каков наиболее эффективный способ сделать это?

примечание: предположим, что A и B имеют фиксированное количество цифр в базе 4, скажем, ровно 16 цифр.

Ответы [ 2 ]

3 голосов
/ 12 февраля 2012

Предположим, ваши интты по 4 байта каждая.32 бита.

Более понятный способ:
Массив констант справки: 

h[0]=3;
for (int i=1; i<7; i++){
  h[i]=h[i-1]*4;
}

Позже, для проверки, если c является целым числом после побитового XOR: 

int count=0;
for (int i=0; i<7; i++){
  if(c&h[i]==0)count++;
}

Другое решение.Очевидно, быстрее, но немного менее понятно: 

int h[4]={1,0,0,0}

int count=0;
for (int i=0; i<15; i++){
  count+=h[c&3];
  c=c>>2;
}

Дальнейшее сгущение: 

count= h[c&3] + h[(c=>>2)&3] + h[(c=>>2)&3] + h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3] + h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c=>>2)&3]+ h[(c>>2)&3];

Еще дальше: 

int h[16]={2,1,1,1, 1,0,0,0, 1,0,0,0, 1,0,0,0};
count= h[c&15] + h[(c=>>4)&15] + h[(c=>>4)&15] + h[(c=>>4)&15]  + h[(c=>>4)&15] + h[(c=>>4)&15] + h[(c=>>4)&15]+ h[(c>>4)&15];

Если вам действительно нужно использовать функциюстолько (10 ^ 10) раз, считайте h [256] (вы уже поймали, как) и используйте: 

count= h[c&255] + h[(c=>>8)&255] + h[(c=>>8)&255] + h[(c>>8)&255] ;

Я думаю, что справочный массив h [256 * 256] также будет пригоден для использованияеще.Тогда 

count= h[c&255] + h[(c>>16)&(256*256-1)];

Массив из 2 ^ 16 дюймов будет весь в процессорных деньгах (правда, третий уровень).Так что скорость будет действительно отличной.

0 голосов
/ 12 февраля 2012

Одним из решений является использование алгоритмов установки количества битов, как предложено Оли. но чтобы адаптировать его к базе 4, мы можем сделать, например:

d = x ^ y;

d = (d | (d >> 1)) & 1431655765; // 1431655765 = (01010101010101010101010101010101) в основании 2

затем посчитайте количество установленных бит в d. это дает количество несоответствий.

Это самый эффективный способ?

...