Summary
Bit manipulation is all about tricks. bitset is also a common data structure in set problems.
Details
Bitwise Not
unsigned char ch = 2;
std::bitset<8> bs(~ch);
// 11111101
std::cout << bs << std::endl;Flip Last Set Bit
The last set bit is the rightmost set bit. i&(i-1) does the trick to reset that bit. It is commonly used in Binary Indexed Tree (BIT).
(i-1) flips all the bits to the right of rightmost 1 in x and also including the rightmost 1.
Power of Two
i&(i-1)==0 => power_2 can also be used to judge if a number is a power of two in O(1) time.
Last Set Bit
i^(i&(i-1)) should work since i&(i-1) flips only the last set bit.
i&(-i) also works. Since (-i) is the two’s complement (one’s complement of i plus 1) of i.
Iterate Subset
Given set S, the following code traverse all the subset in S in O(2^|S|) time. See this post in cp-algorithms.
for (int j = s; j > 0; j = (j - 1) & s) {
printf("%04x\n", j);
}An important conclusion in the post is that the following nested loops will have O(3^n) complexity.
for (int m=0; m<(1<<n); ++m)
for (int s=m; s; s=(s-1)&m)Belong To
To check if bit set of a belongs it of b, we could use (a&b)==a.
Bits Shift
Never shift negative numbers. Never shift negative number of bits.
“For negative a, the behavior of a << b is undefined. “
“For negative a, the value of a >> b is implementation-defined (in most implementations, this performs arithmetic right shift, so that the result remains negative).”
“In any case, if the value of the right operand is negative or is greater or equal to the number of bits in the promoted left operand, the behavior is undefined.”