1 const int mod = 1000;
2
3 int bitpow(int x, int n) {
4 int ans = 1;
5 int t = x;
6 while(n) {
7 if(n & 1) {
8 ans = (ans * t) % mod;
9 }
10 t = t * t % mod;
11 n >>= 1;
12 }
13 return ans;
14 }
15
16 int bitadd(int x, int y) {
17 int xr = x ^ y;
18 int nd = x & y;
19 while(nd) {
20 int xr1 = xr;
21 int nd1 = nd << 1;
22 xr = xr1 ^ nd1;
23 nd = xr1 & nd1;
24 }
25 return xr;
26 }
27
28 int negtive(int x) {
29 return bitadd(~x, 1);
30 }
31
32 int bitminus(int x, int y) {
33 return bitadd(x, negtive(y));
34 }
35
36 int bitmulti(int x, int y) {
37 int ans = 0;
38 while(y) {
39 if(y & 1) {
40 ans = bitadd(ans, x);
41 }
42 x = (x << 1);
43 y = (y >> 1);
44 }
45 return ans;
46 }
47
48 int bitdiv(int x, int y) {
49 int ans = 0;
50 for(int i = 31; i >= 0; i--) {
51 if((x>>i) >= y) {
52 ans += (1<<i);
53 x -=(y<<i);
54 }
55 }
56 return ans;
57 }
