CODEWITHSUNDEEP
algorithmmathbinary
Pteromys
Pteromys

Reputation: 31

count integers whose binary representations differ in exactly k positions from that of a given integer

Given four integers a ≤ b ≤ c and k, how do you count integers in [a, c] whose binary representations differ in exactly k positions from that of b? a, b and c are about 30 bits long.

Upvotes: 3

Views: 296

Answers (4)

Jeffrey Sax
Jeffrey Sax

Reputation: 10323

If you need to compute the count for a given a, b and c, and for all values of k, then I think your best bet is to iterate and count the number of bits in the xor'ed difference.

for (int i = a; i <= c; i++) {
    int d = i ^ b;
    int k = 0;
    while (d != 0) {
        k++;
        d &= (d - 1);
    }
    counts[k]++;
}

You can even parallellize this easily. You would need to keep a separate set of counts for each thread, and add them all up at the end to get the grand totals.

For a range of 1 billion numbers, the parallel version of this algorithm took 3.7 seconds on my machine.

EDIT: Actually, there is a way to get the counts without enumerating. Here's the basic idea for (a,b,c)=(17,25,29), or in binary (10001,11001,11101). First, notice that the range 11000-11011 contains b, and is also entirely contained in (a,c). So these 2^2 values, contribute choose(2,k) to each count. The next interval down is 10100-10111. The numbers in this range all have at least 2 bits different from b, so they contribute choose(2,k-2) to the kth count. The next interval down that is fully contained in (a,c) is 10010-10011, which contributes choose(1,k-1), and so on. You also have to count upwards.

2nd edit: Couldn't resist implementing this. Total time for 1 billion numbers: 0.004ms...

Upvotes: 1

Petar Ivanov
Petar Ivanov

Reputation: 93040

The total count of numbers which differ in exactly k positions from b and are written with at most 30 bits is binomial(30, k). This number is the greatest when k = 15 and is binomial(30, 15) = 155117520, so this is better then enumarating from a to c, but still can be a lot. However if k is small that's the way - just enumerate all these numbers that differ in exactly k bits and check whether they are between a and c. If that's too slow, then you should do it more intelligently - for example if a and c have the same highest bit, then this bit has to be set, so you can reduce the possibiities.

Upvotes: 0

Foo Bah
Foo Bah

Reputation: 26271

Why not just explicitly enumerate all values between a and c, checking how many bits differ for each value? The technical term for this in information theory is Hamming distance http://en.wikipedia.org/wiki/Hamming_distance

Upvotes: 1

jdwhitfield
jdwhitfield

Reputation: 135

Write the binary repr for b, flip k of the bits and check if it violates the bounds. For a,b being 30 bits it shouldn't be prohibitive to write a shell script or a C program so long as k is reasonable.

Upvotes: 0

Related Questions