位运算

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;
}
};