Bitstring Comparison Operation

[Jus144tice]

Hi,

I am looking for the fastest way to compare two bitstrings of equal length and return the number of bits that differ between the two strings. For example:

a = 1011001110001101
b = 0011001010011100

These strings differ in 4 places, so the operation would return 4. Currently, I am taking the XOR of the two strings at each bit position, which would yield:

xor = 1000000100010001

Now, I count the number of 1's to get 4. However, I would like to be able to do this without having to loop through the bits. What I'd really like to do is treat the strings as integers and perform some sort of mathematical operation on them to quickly return the number of different bits.

For example, a and b could be represented as numbers:

a = 45965
b = 12956

I want to define some operator / algorithm (call it @), such that

45965 @ 12956 = 4

Because there are 4 differing bits between the two numbers' binary representation. I would be OK representing the data differently if it would help.

Any thoughts?

[TheCPUWizard]

:rolleyes::rolleyes: What programming language???

[Jus144tice]

Psuedocode. I'm more interested in the theory behind the operation than the actual implemetation. If it does make a difference, I am working with Perl 5.8 connected to an Oracle 10g database, with the ability to use XS to call functions written in C, so I do have access to any functionality provided by any of those. If any other language provides a better solution, that would work as well.

[Jus144tice]

Here's my implemetation of this in C. Given 2 16-bit numbers (source and target) it computes the XOR of the numbers (stored in res) then counts the number of 1 bits and returns that count. The loop is what's killing me though. If there's not a fast numeric operation, maybe there's a different way to represent the bitstrings, perhaps some spacial representation like a vector or something that could be used to compare quickly? I'm not really sure...


int bits = 16;
int source = 45965;
int target = 12956;
int count = 0;
int res = source^target;
int shift,bit;

for (shift=0,bit=1;shift<bits;++shift,bit=1<<shift)
count += ((res&bit)>0);

return count;

[MrViggy]

Are you looking for something like this:

http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

You'd still have to do your XOR, but then you could apply one of the fast bit counting routines. However, if you're not doing this too often, and you always have 16 bit numbers, I'm unsure how much time this would actually save you.

I found this webpage when looking for a way to count the number of bits in an unknown sized integer (could be almost any size). Specifically, I just wanted to know if the count was even or odd.

Viggy