-
Notifications
You must be signed in to change notification settings - Fork 0
/
bits.h
161 lines (139 loc) · 4.03 KB
/
bits.h
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
/*
* bits.h --
*
* algorithms related to the calculation of the bits
*
* Fri Feb 1 10:25:43 PST 2013: initial release by Todd Xue
*/
#ifndef _bits_h
#define _bits_h
/**
* some ugly bits operations
*/
namespace bits {
typedef unsigned int uint;
/**
* using bit to implement add
* so stupid for this one
*/
inline uint add(uint a, uint b) { if (b == 0) return a; uint sum = a ^ b; uint carry = ((a & b) << 1); return add(sum, carry); }
/**
* compare without using > < operator, but can C operators: -, bits
*/
inline bool lt(uint a, uint b) { return (a - b) & (1 << 31); }
inline bool gt(uint a, uint b) { return !lt(a, b); }
inline uint max(uint a, uint b) { return lt(a,b) ? b : a; }
inline uint min(uint a, uint b) { return a + b - max(a, b); }
/**
* swap using ^, in Z/2, it's same as -, + WITHOUT extra storage
* (a, b) -> (a-b, b) -> (a-b, a) -> (b, a)
*
* If inline really succeeded, then it really does it without extra storage
*
* i'm confused at the beginning, now clarify as this:
*
* in Z/2
* ^ + or -
* | max
* & min
* ~ no mapping, seems
*
* the codes written below is weird, without looking the above logic, how we know it works :(???
*/
inline void swap(uint& a, uint& b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
/**
* using bit to decide if a uinteger is power of 2
*/
inline bool is_2_power(uint a) { return (a & (a-1)) == 0; }
/**
* log2
* Note:
* log2(0, 1) -> 0 --> 2^^?
* log2(2, 3) -> 1 --> 2^^0
* log2(4, 5, 6, 7) --> 2 --> 2^^2 = 4
* No way to return a good value to log2(0) :(
*/
inline uint log2(uint a) { uint c = 0; while (a >>= 1) ++c; return c; }
/**
* right most 1 pos
*/
inline uint right_most_1_pos(uint a) { if (!a) return 32; uint pos = 0; while ((a & 1) == 0) a >>= 1, ++pos; return pos; }
/**
* Number of bit 1
* 3 --> 2
* 4 --> 1
*
* There are a lot of solutions for this one, reference to http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html
* one is like this one:
*
* unsigned int tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
* return ((tmp + (tmp >> 3)) & 030707070707) % 63;
*
* another one is:
* { c = 0; for (; n > 0; n &= n-1) ++c; return c; }
*/
inline uint number_of_bit1(uint a) { uint c = 0; while (a > 0) { c += (a & 0x1); a >>= 1; } return c; }
inline uint number_of_bit0(uint a) { return (uint)(sizeof(uint)/sizeof(char)*8 - number_of_bit1(a)); }
/**
* next smallest number with same number of 1 bits
* return 0 if there is no next number
*/
inline uint next_smallest(uint a) {
if (a == 0)
return 0;
/**
* 0 1 1 1 0 0 0 0
* ^
* p1
*/
uint p1 = right_most_1_pos(a);
/**
* 0 1 1 1 0 0 0 0
* ^
* ^ p1
* p2
*/
uint p2 = p1+1;
while (p2 < 32 && (a & (1 << p2)) > 0) ++p2;
if (p2 == 32)
return 0;
uint b = a;
/**
* turn on p2 bit
*
* 1 1 1 1 0 0 0 0
* ^
* p2
*/
b |= (1 << p2);
/**
* turn off [0, p2)
*
* 1 0 0 0 0 0 0 0
* ^
* p2
*/
b &= ~((1 << p2) - 1);
/**
* turn on all removed bits to lowest bits
*
* 1 0 0 0 0 0 1 1
* ^
*/
if (p2 - p1 > 1)
b |= ((1 << (p2 - p1 - 1)) - 1);
return b;
}
/**
* previous largest number with same number of 1 bits
* return 0 if there is no next number
*
* the reverse of next_smallest, turns out a simpler :)
*/
inline uint prev_largest(uint a) { return ~next_smallest(~a); }
}
#endif