Title: Theory / Unimportant / CS / Algo / Hacker's delight{ / 05 Counting bits
Tags: expressionButNoExpression2 toBinary

Page: 67
Variables: \(b\ge2\) a basis (radix)
\(x\) a \(n\)-bit number in basis \(b\)
Expression: x=x-((x>>1)&0x55555555);
x=(x&0x33333333)+((x>>2)&0x33333333)
x=(x+(x>>4))&0x0F0F0F0F;
x=x+(x>>8)
x=(x>>16);
return x&0x0000003F
Chapter: 5
Section: 1
Binary: number of 1 in the number
Notation: sum_digits(x)
Numeric: \(x-(b-1)\sum_{i=0}^{n-1}\left\lfloor\frac{x}{b^{i}}\right\rfloor\)
Abbreviation: \(pop(x)\)

Page: 65-69
Variables: \(x\) a 32-bit variable
Expression: unsigned n
n=(x>>1)&0111 0111 0111 0111 0111 0111 0111 0111;
x=x-n
n=(x>>1)&0111 0111 0111 0111 0111 0111 0111 0111;
x=x-n
n=(x>>1)&0111 0111 0111 0111 0111 0111 0111 0111;
x=x-n
x=(x+(x>>4))& 0000 1111 0000 1111 0000 1111 0000 1111;
x=(x+(x>>4))&030707070707;
x=x*0000 0001 0000 0001 0000 0001 0000 0001;
return x>>24
Chapter: 5
Section: 1
Binary: Population count of \(x\)
Expression2: \(x-\sum_{i=0}^{31}\left\lfloor\frac{x}{2^{i}}\right\rfloor\)
Expression3: x=x-((x>>1)&0x55555555);
x=(x&0x33333333)+((x>>2)&0x33333333)
x=(x+(x>>4))&0x0F0F0F0F;
x=x+(x>>8)
x=(x>>16);
return x&0x0000003F
Expression4: unsigned n
n=(x>>1)&03333333333;
x=x-n
n=(x>>1)&03333333333;
x=x-n
x=(x+(x>>3))&030707070707;
return x% 63
longs numbers in octal
Abbreviation: \(pop(x)\)