Population count between two positions

Question

I am looking for a solution of finding pop count in bitstring between two positions eg:

popcnt( 10(0101), 0, 3) = 1
popcnt( 100101(), 0, 0) = 0
popcnt( 10010(1), 0, 1) = 0

** I am assuming open range and assuming Right to Left order

using standard bit operators and possibly popcnt or equivalent.

If it makes difference, I am looking to find the popcnt between the difference of two strings. Lets say i have string b and i swap bits in two positions, eg 0101110 -> 1101100 => 3 - I need the popcnt between the bits that changed - in the case of 0101110 -> 1101100 the bits between the two are 10110 and so popcnt is 3

Do you see some ingenious way to do so with bithacks?

Not sure I'm reading this right. XOR the strings and count the numbers of bits set in the result ? — cnicutar, Dec 05 '12 at 17:41
@cnicutar that tells you difference pocnt, not popcnt between difference — Anycorn, Dec 05 '12 at 17:42
Check this [link](http://bits.stephan-brumme.com/countBits.html). — Sunil Bojanapally, Dec 05 '12 at 17:43
@iccthedral I'm currently confused by that too.@Anycom Are the binary strings to be read from R to L or L to R? — James, Dec 05 '12 at 17:43
@iccthedral there are no bits between 0 and 1, so it should be 0 — Anycorn, Dec 05 '12 at 17:44
If there are no bits between 0 and 1, how is (0, 0) different from (0, 1) ? — cnicutar, Dec 05 '12 at 17:46
@cnicutar they aren't, such is the requirement of the domain — Anycorn, Dec 05 '12 at 17:47
@Anycom Can you make bold the digits that are being counted in your three examples? I'm currently bamboozled. — James, Dec 05 '12 at 17:50
@Anycorn, what do you mean exactly by "possibly popcnt or equivalent"? Are you looking for an opcode? — nullpotent, Dec 05 '12 at 17:50
@Anycorn thanks for the clarification, now I see. You can just AND them together (&) and then use the answer below. — Gille, Dec 05 '12 at 17:57
What do you mean by "pop count"? The meaning I know (and assumed in my answer) is "number of `1` bits", but this contradicts the examples after you edited the question. — interjay, Dec 05 '12 at 18:09
@interjay sorry, i have made few typos, been staring at screen too long. the ansdwer you gave me is what works for me. — Anycorn, Dec 05 '12 at 18:11
Please, correct your examples and explain role of parameters... for( bitrank=2nd-param,bitrank<3rd-param) or 3rd-param is length? — aka.nice, Dec 05 '12 at 22:08
Also correct 0101110 -> 1101100 => 3, and explain what is 3. After Gill comment, I still do not understand. You changed bit of rank 2 and bit of rank 7, so there are only 4 bits that did not change from rank 3 to 6 inclusive, that is string 1011. You seem to include bit of rank 2 and exclude bit of rank 7 and consider the popcount of string AFTER change 10110, that's very confusing, is it really your intention? — aka.nice, Dec 05 '12 at 22:14

score 7 · Accepted Answer · edited May 23 '17 at 12:15

7

First mask the value to get only the relevant bits:

relevant = (value >> startBit) & ((1 << numOfBits) - 1);

Edit:

The above will invoke undefined behavior when numOfBits == 32 (or more accurately, when numOfBits == CHAR_BIT * sizeof(int)). To fix this you need to have special handling for that case (set relevant = value).

Then find the population count of those bits using one of the methods proposed in this question: Best algorithm to count the number of set bits in a 32-bit integer.

To summarize the answers, You can use a platform-specific function such as GCC's __builtin_popcount, or if you need a portable solution you can use a parallel-prefix algorithm such as the one from Matt Howells's answer:

int NumberOfSetBits(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

edited May 23 '17 at 12:15

Community

1
1

answered Dec 05 '12 at 17:50

interjay

107,303
21
270
254

Thanks, I am trying to understand the logic now – Anycorn Dec 05 '12 at 17:57
1

It's just a matter of style, but I usually like this form: relevant = (value >> startBit) &~ (-1 << numOfBits) – Juan Lopes Dec 05 '12 at 18:22
What happens when you want 32 bits popcount(x,0,32) ? Does ((1 << numOfBits) - 1); works ? – aka.nice Dec 05 '12 at 21:55
@aka.nice: That's indeed an issue: According to the C standard it would be undefined behavior, though I believe that on x86 processor it should give the correct result. I'll replace it with a portable version. – interjay Dec 05 '12 at 23:31
1

Actually it gives the wrong result on x86, so the fix will still be needed. – interjay Dec 05 '12 at 23:46
Instead of masking, you could also do a 2nd shift to knock bits off the high side of the value. (popcnt doesn't care where the bits are). Shift right by `startBit`, then shift left by `32-numOfBits`. (where 32 is actually derived from `CHAR_BIT`). This only has undefined behaviour when `numOfBits` is zero. – Peter Cordes Feb 14 '16 at 22:58

Population count between two positions

1 Answers1