🔒 Locked

fast bitset distances

Started by __tunjin__ Jan 17, 2003 at 9:10 AM 4 replies 400+ views

Original Post

Jan 17, 2003 at 9:10 AM

i have two 32 bit numbers. between them i want to calculate their distance - distance ist simply the number of bits that are not equal. my curren (naive) implementation:

unsigned long tmp = x1 ^ x2;
int d=0;
for(int i=0; i 

this is quite slow, especially because i have to do it up to 2^num_important_bits * 500 times...

any way to speed it up?

Neophyte

Jan 17, 2003 at 9:39 AM

  
#include <bitset>

int main() {
    unsigned int x1, x2;
    x1 = 578464;
    x2 = 68587;
    int d = (bitset<32>(x1) ^ bitset<32>(x2)).count();
}

Quick naive speedtest on linux using gcc indicates that that version is something like 50% faster than your current implementation when optimization is turned off, and about 5 times faster with optimization turned on.

-Neophyte

__tunjin__

Jan 17, 2003 at 9:53 AM

cool, works perfectyl - because I was just spicing up some old C - code I totally forgott about stl ;-)

thanks

S1CA

Jan 17, 2003 at 9:59 AM


unsigned int d = x1 ^ x2;
d = (d & 0x55555555) + ((d & 0xaaaaaaaa) >> 1);
d = (d & 0x33333333) + ((d & 0xcccccccc) >> 2);
d = (d & 0x0f0f0f0f) + ((d & 0xf0f0f0f0) >> 4);
d = (d & 0x00ff00ff) + ((d & 0xff00ff00) >> 8);
d = (d & 0x0000ffff) + ((d & 0xffff0000) >> 16);

Assuming a 32bit integer.

You could also early out by testing immediately after the d=x1^x2:

a) if d==0 skip the rest
b) if ((d&(d-1))==0) then d=1

depending on how much the branch prediction costs in your app.

If you''re performing this on a lot of integers, the masking and shifting above is PERFECT for MMX optimisation, i.e. test lots of values in parallel.

Although all this will win you some performance points, I''d actually look higher up the code and ask if you NEED the difference between the bits, and if you need it as a definate count - for example maybe having the positions or 2^position of the differences is enough. Always look higher and you''ll get 1000s of % difference rather than 10s of % difference!

--
Simon O''Connor
Creative Asylum Ltd
www.creative-asylum.com

__tunjin__

Jan 18, 2003 at 7:57 AM

thanx a lot...

simon:
* unfortunately i have to calculate all distances because i need to find a perfect distribution - statistics stuff...
* your solution always returns distance *2 - because i write this on linux?

[edited by - __tunjin__ on January 18, 2003 9:00:13 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.