1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// 最低位的1 ->                  x&-x
// 去掉最低位的1 ->               x&(x-1)
// 有效数字全是1 ->               (x&(x+1))==0
//把最低位的0 变成1->              x|(x+1)
//取出最低位的0并变成1             (~x)&(x+1)
//取出第k位（约定最低位为第0位）     x&(1<<k)


/* all
 
 bit cnt one            ->      cnt_one(x)              ->  int __builtin_popcount (unsigned int x);
 bit rev                ->      rev_dig(x)              ->
 high bit               ->      high_one(x)
 count leading zero     ->      cnt_leading_zero(x)     ->  int __builtin_clz (unsigned int x);
 count trailing zero    ->      cnt_trailing_zero(x)    ->  int __builtin_ctz (unsigned int x);
 get trailing one       ->      get_trailing_one(x)     ->  x&(x^(x+1))
 
 */
typedef unsigned int u32;
namespace bit{
    
    //count the digits of one in binary number
    u32 co[65536u];//bit cnt one
    void cnt_one_ini() {
        for (u32 i = 1; i < 65536u; i++)
            co[i] = co[i >> 1] + (1 & i);
    }
    u32 cnt_one(u32 x) {
        return co[x & 0xffffu] + co[x >> 16];
    }
    
    
    //reverse the digits in binary number
    u32 rd[65536u];//bit rev data
    void rev_digit_ini() {
        for (u32 i = 1; i < 65536u; i++)
            rd[i] = (rd[i >> 1] >> 1) | ((i & 1) << 15);
    }
    u32 rev_dig(u32 x) {
        return rd[x >> 16] | (rd[x & 0xffffu] << 16);
    }
    
    
    //get the highest digit one in binary number
    u32 ho[65536u];//high bit data
    void high_one_ini(){
        ho[1]=1;
        for(u32 i=2;i<65536u;i++){
            ho[i]=ho[i>>1]<<1;// only the one have the highest digit one 1;
        }
    }
    u32 high_one(u32 x){
        return x<65536u ? ho[x]:(ho[x>>16]<<16);
    }
    
    
    //count leading zero
    u32 clz[65536u];//leading zero count
    void cnt_leading_zero_int(){
        clz[0]=16;
        for(u32 i=1;i<65536u;i++){
            clz[i]=clz[i>>1]-1;
        }
    }
    u32 cnt_leading_zero(u32 x){
        if(x<65536u){
            return clz[x]+16;
        }
        else {
            return clz[x>>16];
        }
    }
    
    //count trailing zero
    u32 ctz[65536u];//trailing zero count
    void cnt_trailing_zero_int(){
        ctz[0]=16;
        for(u32 i=1;i<65526u;i++){
            ctz[i]=i&1 ? 0: ctz[i>>1]+1;
        }
    }
    u32 cnt_trailing_zero(u32 x){
        if(x<65536u){
            return ctz[x];
        }
        else {
            return ctz[x&65535u];
        }
    }
    
    //count leading one is more diffcult using count leading zero
    
    
    //提取第k个1
    int kthbit(u32 x, int k) {
        int s[5], ans = 0, t;
        s[0] = x;
        s[1] = x - ((x & 0xAAAAAAAAu) >> 1);
        s[2] = ((s[1] & 0xCCCCCCCCu) >> 2) + (s[1] & 0x33333333u); s[3] = ((s[2] >> 4) + s[2]) & 0x0F0F0F0Fu;
        s[4] = ((s[3] >> 8) + s[3]) & 0x00FF00FFu; t = s[4] & 65535u;
        if (t < k) k -= t, ans |=16, x >>=16;
        t = (s[3] >> ans) & 255u;
        if (t < k) k -= t, ans |= 8, x >>= 8; t = (s[2] >> ans) & 15u;
        if (t < k) k -= t, ans |= 4, x >>= 4; t = (s[1] >> ans) & 3u;
        if (t < k) k -= t, ans |= 2, x >>= 2; t = (s[0] >> ans) & 1u;
        if (t < k) k -= t, ans |= 1, x >>= 1; return ans;
    }
};