Who can help explain the principles of this program do?

arcanelove

int bits_set (int word)
{
int tmp;
tmp = (work >> 1)&033333333333;
tmp = word-tmp-((tmp >> 1)&033333333333);
return (((tmp + (tmp >> 3))&030707070707)% 077);
}

An input function of this procedure is an integer, and then determines the number of binary 1 represents an integer of this.
Please help explain the principle of the program, what's the last% 077
thank you all

stoneboy4000

Hacker's delight
First calculate the number of 1 with 2bits as a group and put them in these 2bits;
Then use 4bits as a group to calculate the number of 1s in the adjacent two groups of 2bits;
Then take 8bits as a group, calculate the number of 1 in the two adjacent groups of 4bits, and so on.
As follows:
10 11 11 00 01 10 00 11 01 11 11 10 11 11 11 11
01 | 10 | 10 | 00 | 01 | 01 | 00 | 10 | 01 | 10 | 10 | 01 | 10 | 10 | 10 | 10
00 11 | 00 01 | 00 10 | 00 10 | 00 11 | 00 11 | 01 00 | 01 00
00 00 01 00 | 00 00 01 00 | 00 00 01 10 | 00 01 00 00
00 00 00 00 00 00 10 01 00 00 00 00 00 00 11 10
00 00 00 00 00 00 00 00 00 00 00 00 00 01 01 11

C program:
x = x&0x55555555 + (x >> 1)&0x55555555;
x = x&0x33333333 + (x >> 2)&0x33333333;
x = x&0x0F0F0F0F + (x >> 4)&0x0F0F0F0F;
x = x&0x00FF00FF + (x >> 8)&0x00FF00FF;
x = x&0x0000FFFF + (x >> 16)&0x0000FFFF;

copy from jingya_feng

Some are similar, please refer to it ^ _ ^

arcanelove

I understand the process and results of this program
But I don't know the principle is why writing this way can achieve the result, please master the guidance

KTPOPO

After reducing the cyclic accumulation intensity with the divide and conquer method, the result is this ...
Turn what was originally calculated one by one into parallel computing.

KTPOPO

After reducing the cyclic accumulation intensity with the divide and conquer method, the result is this ...
Turn what was originally calculated one by one into parallel computing.

stoneboy4000

Long live

For this problem, the process is the principle. It should be the same as other formula theorems. When someone asks a question, someone studies it, so there is this algorithm.
In fact, it is likely to be exhaustive to prove
ps: This conclusion is purely speculation, if there is similarity, it is purely accidental ^ _ ^

吉娃娃

It seems that everyone does not understand the principles of computer composition (data format), operating systems (system platform differences), and mathematical knowledge.

arcanelove

It seems that everyone does not understand the principles of computer composition (data format), operating systems (system platform differences), and mathematical knowledge

____________________________________________

Could you please explain it a bit? Thank you

天魔狂舞

I understand.
mark