What is the fastest way to count the number of matching digits in a 4 base?

Question

Given two unsigned integers, what's the fastest way to count the number of matching digits in a base representation of 4?

example 1:

A = 13 = (31) in base 4

B = 15 = (33) in base 4

the number of matching digits in base 4 is 1.

Example 2:

A = 163 = (223) in base 4

B = 131 = (203) in base 4

the number of matching digits in base 4 is 2.

The first step, in my opinion, is to calculate the bitwise XOR of two integers, then we need to calculate a number from 00 pairs? What is the most efficient way to do this?

Note: Assume that A and B have a fixed number of digits in the base 4, say exactly 16 digits.

Answer 1

Suppose your ints are 4 bytes each. 32 bit

A more understandable way:
Help: persistent array:

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

Later to check if c is an integer after bitwise XOR:

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

Another solution. Obviously faster, but a little less clear:

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

Further qickening:

 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]; 

Besides:

 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]; 

If you really need to use the function so many (10 ^ 10) times, read h [256] (you already caught how) and use:

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

I think the h [256 * 256] help array will also be useful. Then

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

An array of 2 ^ 16 ints will be all in the processor's cash (third level, though). Thus, the speed will be very high.

Answer 2

One solution is to use the algorithms for counting given bits proposed by Olya. but to adapt it to base 4, we can do, for example:

d = x ^ y;

d = (d | (d → 1)) & 1431655765; // 1431655765 = (0101010101010101010101010101010101) in base 2

then count the number of set bits in d. this gives a number of inconsistencies.

Is this the most effective way?