1. Binary state compression
Binary state compression refers to compressing a file with a length of
m
m
The bool array of m uses a
m
m
A method of representing and storing m-bit binary integers.
The following bit operations can be used to access the corresponding subscript elements in the original bool array.
| Operation | Operation |
|---|---|
| Get the integer
n n n in binary representation k k k bits |
(n >> k) & amp; 1 |
| Get the integer
n n n in binary representation 0 0 0 ~ k ? 1 k-1 k?1 bit |
n & amp; ((1 << k) - 1) |
| Put the integer
n n n in binary representation k k K bit negation |
n ^ (1 << k) |
| For integers
n n n in binary representation k k k-bit assignment 1 |
n | (1 << k) |
| pair of integers
n n n in binary representation k k k bit assignment 0 |
n & amp; (~(1 << k)) |
This method is simple to operate and saves program running time and space. when
m
m
When m is not too large, you can directly use an integer type to store it. when
m
m
When m is large, you can use several integer types (int arrays), or you can directly use the bitset implementation provided by C++ STL.
2. Pairwise transformation
For non-negative integers
n
n
n：
- when
n
n
When n is an even number,
n ^ 1is equal ton
+
1
n+1
n+1
- when
n
n
When n is an even number,
n ^ 1is equal ton
?
1
n-1
n?1
Therefore, “0 and 1” “2 and 3” “4 and 5” … operations on ^ 1 constitute “pairwise transformations”.
This property is often used to store edge sets in graph theory adjacency lists. In a graph with undirected edges (bidirectional edges), store a pair of forward and reverse edges in the adjacency list array.
n
n
n and
n
+
1
n+1
n + 1 position (where
n
n
n is an even number), you can obtain the current edge through the operation of ^ 1
(
x
,
y
)
(x, y)
(x,y) opposite side
(
y
,
x
)
(y,x)
The storage location of (y,x).
3. Lowbit operation
lowbit(n) is defined as a non-negative integer
n
n
n is a numerical value composed of “the lowest bit 1 and all following 0s” in binary representation. Such as
n
=
10
n=10
The binary representation of n=10 is
(
1010
)
2
(1010)_2
(1010)2?, then
l
o
w
b
i
t
(
n
)
=
2
=
(
10
)
2
lowbit(n) = 2 = (10)_2
lowbit(n)=2=(10)2?.
Derivation
l
o
w
b
i
t
(
n
)
lowbit(n)
The formula for lowbit(n).
set up
n
>
0
n > 0
n>0，
n
n
nth
k
k
The k bit is 1, and the
0
0
0 ~
k
?
1
k-1
The k?1 bits are all 0.
In order to implement lowbit operations, first
n
n
n is negated, at this time the
k
k
k becomes 0, and the
0
0
0 ~
k
?
1
k-1
The k?1 bits are all 1. Order again
n
=
n
+
1
n = n + 1
n=n + 1, at this time because of carry, the
k
k
k is changed to 1, the 0th ~
k
?
1
k-1
The k?1 bits are all 0.
After taking the inverse and adding 1 operation above,
n
n
nth
k
+
1
k+1
k + 1 bit to the highest bit is exactly the opposite of the original, so n & amp; (~n + 1) only has the
k
k
The k bits are 1, and the remaining bits are 0. In two’s complement representation, ~n = -1 - n, therefore
?lowbit(n) = n & amp; (~n + 1) = n & amp; (-n)
lowbit operation combined with Hash can find all the bits that are 1 in the binary representation of the integer, and the time spent is the same as the number of 1’s. To achieve this goal, just continue to assign n to n – lowbit(n) until
n
=
0
n=0
n=0.
For example, n = 9 = (1001)2, then lowbit(9) = 1. Assign n to 9 – lowbit(9) = 8 = (1000)2, then lowbit(8) = 8 = (1000)2. At this time 8 – lowbit(8) = 0, stop looping. In the whole process, two numbers, 1 and 8 = (1000)2, are subtracted, which are exactly the values obtained by adding 0 after the 1 in each bit of n. Taking the logarithms of 1 and 8, log21 and log28, we get
n
n
Bits 0 and 3 of n are 1. Because the log function of the C++ math.h library is a real number operation with e as the base, and the complexity constant is large, it is necessary to preprocess an array and replace the log operation with the Hash method.
When n is small, the simplest method is to directly create an array H, let H[2k] = k, the program is as follows:
const int MAX_N = 1 << 20;
int H[MAX_N + 1];
for (int i = 0; i <= 20; i + + ) H[1 << i] = i; //Preprocessing
while (cin >> n) {<!-- -->
while (n > 0) {<!-- -->
cout << H[n & amp; -n] << ' ';
n -= n & -n;
}
cout << endl;
}
A slightly more complicated but more efficient method is to create an array H of length 37, let H[2 k mod 37] = k. A little math trick is used here:
?
k
∈
[
0
,
35
]
,
2
k
\forall k \in [0,35], 2^k
?k∈[0,35],2k mod 37 are not equal to each other, and they take exactly 1 ~ 36. The required procedures are:
int H[37];
for (int i = 0; i < 36; i + + ) H[(1ll << i) % 37] = i;
while (cin >> n) {<!-- -->
while (n > 0) {<!-- -->
cout << H[n & amp; -n] << ' ';
n -= n & amp; -n;
}
cout << endl;
}
It is worth pointing out that lowbit operation is also a basic operation in tree arrays.