#include #include // human output ONLY, NOT for bithack // SUPPORT code. See comments for submitted solution. // // Bit hack using parallel bit-count population algorithm // see notes following code for assembly source // Input: An integer. Try 127. Or 77777. using namespace std; int main() { unsigned long v, x, c; char NL = '\n'; cout << "A 32-bit integer's bits to count in parallel: "; cin >> v; unsigned long original_v = v; // The algorithm with final substitutions v = v - ((v >> 1) & 0x55555555); x = (v & 0x33333333) + ((v >> 2) & 0x33333333); c = ((x + (x >> 4) & 0x0F0F0F0F) * 0x01010101) >> 24; cout << NL << "For input: " << original_v << NL; cout << "Binary representation: " << bitset<32>(original_v) << dec << NL; cout << "The population is: " << c << endl; cout << "Bonus: Most significant bit: "; int msb; asm("bsr %1,%0" : "=r"(msb) : "r"(original_v)); cout << msb; return 0; } /* Related to challenge https://www.sololearn.com/Discuss/622449/?ref=app Algorigthm adapted from machine language / assembly CPU source: Software Optimization Guide for AMD Athlon 64 and Opteron processors Section 8.6: Efficient Implementation of Population-Count Function in 32-Bit Mode http://support.amd.com/techdocs/25112.pdf "Population count is an operation that determines the number of set bits in a bit string. For example, this can be used to determine the cardinality of a set. The example code in this section shows how to efficiently implement a population count operation for 32-bit operands. " Assembly Language (returns unsigned int): mov eax, [v] mov edx, eax shr eax, 1 ; v >> 1 and eax, 055555555h ; (v >> 1) & 0x55555555 sub edx, eax ; w = v - ((v >> 1) & 0x55555555) mov eax, edx ; w shr edx, 2 ; w >> 2 and eax, 033333333h ; w & 0x33333333 and edx, 033333333h ; (w >> 2) & 0x33333333 add eax, edx ; x = (w & 0x33333333) + ((w >> 2) & 0x33333333) mov edx, eax ; x shr eax, 4 ; x >> 4 add eax, edx ; x + (x >> 4) and eax, 00F0F0F0Fh ; y = (x + (x >> 4) & 0x0F0F0F0F) imul eax, 001010101h ; y * 0x01010101 shr eax, 24 ; population count = (y * 0x01010101) >> 24 mov retVal, eax ; Store result. c original int v ; // input...ints all through w = v - ((v>>1) & 0x55555555); x = (w & 0x33333333) + ((w >> 2) & 0x33333333); y = (x + (x >>4) & 0x0F0F0F0F); c = (y * 0x01010101) >> 24; c substitute y int v ; // input...ints all through w = v - ((v>>1) & 0x55555555); x = (w & 0x33333333) + ((w >> 2) & 0x33333333); c = ((x + (x >> 4) & 0x0F0F0F0F) * 0x01010101) >> 24 see code for final substitution */

Quarks [algorithm source] : Parallel bitcount + assembly MSB [challenge]