Bit Manipulation Tricks


Bit manipulation is all about tricks. bitset is also a common data structure in set problems.


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.

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.”

Leave a Reply

Your email address will not be published. Required fields are marked *