2

I'm trying to determine if a bitstring, say 64 bit long, is at least 50% ones. I've searched around and looked at the great http://graphics.stanford.edu/~seander/bithacks.html, but I haven't found anything specifically for this problem.

I can split the string up into 8bit chunks, pre-calculate the number of 1s in each, and then find the result in 8 lookups and 7 additions.

Example of bytewise approach:

10001000 10000010 00111001 00001111 01011010 11001100 00001111 11110111
2      + 2      + 4      + 4      + 4      + 4      + 4      + 7        = 31
    hence 0 dominates.

I just feel like there must be a better way given I just want to find the dominator. Maybe I'm just using the wrong name?

Thomas Ahle
  • 30,774
  • 21
  • 92
  • 114
  • Well you're really just counting the 1's, right? And then compare with 32. There are other ways the count the number of 1's even on the page you linked to, this way is in there too – harold Jun 28 '14 at 15:55
  • The point is that I don't want to count them. I just want to find out if there are more 1s than 0s. Hopefully this is a more simple problem. – Thomas Ahle Jun 28 '14 at 15:58
  • Maybe, but counting definitely works and there are efficient ways to do that. – harold Jun 28 '14 at 16:07
  • Right, just not as fast as calculating the parity, say. I was just wondering if there was a specific way to do it. Should I edit my question to clarify this? – Thomas Ahle Jun 28 '14 at 16:22
  • 1
    If you want. I'll think some more about this, there might be some trick I'm not thinking of right now – harold Jun 28 '14 at 16:30

2 Answers2

2

You can use the divide and concur solution here, which is easy adaptable to 32-bit. Or maybe just a popcnt instruction depending on your hardware. Then you just check if that value is less than 32, if so 0s dominate, otherwise 1s dominate.

The code from the link adapted to 64-bit and with the domination logic inserted: (I've bit shifted right by an extra 5 bits at the end to check if the set bits is greater than 31 in the same shift)

int AtLeastHalfOnes(long long i) {
  i = i - ((i >> 1) & 0x5555555555555555LL);
  i = (i & 0x3333333333333333LL) + ((i >> 2) & 0x3333333333333333LL);
  return (((i + (i >> 4)) & 0x0F0F0F0F0F0F0F0FLL) * 0x0101010101010101LL) >> 61;
}
Community
  • 1
  • 1
Apriori
  • 2,308
  • 15
  • 16
  • `b ? true : false` is a bit superfluous isn't it? :) But right, this is another version of 'just use bit counting'. Maybe you are right, that it is fast enough. – Thomas Ahle Jun 30 '14 at 21:57
  • @Thomas Ahle: It is redundant, but the idea is to avoid the conversion to bool performance warning the compiler will generate. Alternatively, the function can be modified to return a zero/non-zero int. I may make this modification above. Also: I don't think you can do it faster than bit counting. The divide and contour method can't work if you throw away counts because you can't merge smaller pieces of that problem. Furthermore, if you just use a popcnt instruction instead (the __popcnt64 intrinsic)... well you're going to have a hard time beating that with any software solution. – Apriori Jun 30 '14 at 22:50
0

I think it is better to use Stack data structure. When your input bit is 1, then push(1);. Otherwise pop(); from top of your stack. Finally if your stack is not empty, I think your problem solved.

Mehdi Algholipour
  • 110
  • 11
  • 2
    Interesting, but how is that better than the solution given in the question? Now you've got a stack to worry about and you have to iterate over all bits. You're just using that stack as a counter anyway. – harold Jun 28 '14 at 16:11