Counting ones in a binary number. N = 1 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 0 1 1 0 0 0 1 How many of those 32 bits are set to 1? Obvious (brute force) method mask = 1 total = 0 while (mask != 0) { if (mask & N) total += 1; mask <<= 1; } each step one comparison (!=) one bitwise and one add one shift one loop. 32 steps, 160 operations. Clever method In an abstract way, the letters A-Za-f represent the individual 32 bits of N. We and N with an alternating 0101010101... pattern N ABCDEFGHIJKLMNOPQRSTUVWXYZabcdef 0x55555555 01010101010101010101010101010101 & 0B0D0F0H0J0L0N0P0R0T0V0X0Z0b0d0f and we do the same after shifting N right by 1 bit N>>1 0ABCDEFGHIJKLMNOPQRSTUVWXYZabcde 0x55555555 01010101010101010101010101010101 & 0A0C0E0G0I0K0M0O0Q0S0U0W0T0a0c0e all the individual bits have survived, but in different places. The letters are only single digits, so by definition they equal to the number of 1 bits in the area they covered. Each bit's value is at most 1, so adding them can produce at most 2. Also, they have neighbouring zeros so they occupy two bits. For any pair A, B, A+B can not be more than 2. The sum will fit in the 2 bits that the numbers already occupy. 0B0D0F0H0J0L0N0P0R0T0V0X0Z0b0d0f 0A0C0E0G0I0K0M0O0Q0S0U0W0Y0a0c0e + AACCEEGGIIKKMMPPRRTTVVXXYYaaccee so now, AA = number of 1s in first two bits of N CC = number of 1s in second two bits of N ... ee = number of 1s in last two bits of N This new number is treated in exactly the same way, but as its useful information is in 16 two-bit pairs, the alternating pattern is now 00110011001100110011001100110011 or 0x33333333 and the shift is by two bits. N1 AACCEEGGIIKKMMPPRRTTVVXXYYaaccee 0x33333333 00110011001100110011001100110011 & 00CC00GG00KK00PP00TT00XX00aa00ee N1>>2 00AACCEEGGIIKKMMPPRRTTVVXXYYaacc 33333333 00110011001100110011001100110011 & 00AA00EE00II00MM00RR00VV00YY00cc Already seen that AA and CC have maximum value 2, so AA+CC is at most 4. The number 4 can be stored in three bits, but we have a total of 4 bits available for each pair, so adding as a single int will also correctly add the 16 pairs of 2. 00CC00GG00KK00PP00TT00XX00aa00ee 00AA00EE00II00MM00RR00VV00YY00cc + 0AAA0EEE0III0MMM0RRR0VVV0YYY0ccc AAA = number of 1s in first 4 bits EEE = number of 1s in second 4 bits ... ccc = number of 1s in last 4 bits Same again, four-bit groups now, so pattern is 0F0F0F0F and shift is 4 N2 0AAA0EEE0III0MMM0RRR0VVV0YYY0ccc 0x0F0F0F0F 00001111000011110000111100001111 & 00000EEE00000MMM00000VVV00000ccc N2>>4 00000AAA0EEE0III0MMM0RRR0VVV0YYY 0x0F0F0F0F 00001111000011110000111100001111 & 00000AAA00000III00000RRR00000YYY AAA and EEE have maximum value 4, so AAA+EEE is maximum 8. Needs 4 bits to store and we have 8 available. 00000EEE00000MMM00000VVV00000ccc 00000AAA00000III00000RRR00000YYY + 0000AAAA0000IIII0000RRRR0000YYYY AAAA = num of 1s in first 8 bits IIII = num of 1s in first 8 bits ... YYYY = num of 1s in last 8 bits eight-bit groups, so pattern is 0x00FF00FF and shift is 8 N3 0000AAAA0000IIII0000RRRR0000YYYY 0x00FF00FF 00000000111111110000000011111111 & 000000000000IIII000000000000YYYY N3>>8 000000000000AAAA0000IIII0000RRRR 0x00FF00FF 00000000111111110000000011111111 & 000000000000AAAA000000000000RRRR AAAA, IIII, etc obviously max 16, needs 5 bits, got 16. 000000000000IIII000000000000YYYY 000000000000AAAA000000000000RRRR + 00000000000AAAAA00000000000RRRRR AAAAA = num of 1s in first 16 bits RRRRR = num of 1s in last 16 bits pattern now 0000FFFF, shift now 16 N4 00000000000AAAAA00000000000RRRRR 0x0000FFFF 00000000000000001111111111111111 & 000000000000000000000000000RRRRR N4>16 000000000000000000000000000AAAAA 0000FFFF 00000000000000001111111111111111 & 000000000000000000000000000AAAAA AAAAA, IIIII max 16 so sum max 32, needs 6 bits, 32 available 000000000000000000000000000RRRRR 000000000000000000000000000AAAAA + 00000000000000000000000000AAAAAA AAAAAA0 is number of 1s in whole 32 bits each step = one shift, two bitwise and, one add. 5 steps, total 20 operations.