Bits important methods/tricks

Bits important methods/tricks

Here are some important tricks on Bits 

1. To multiply/divide an integer by 2 we need to only shift the bits in the integer left/right respectively/

2. To set/turn-on the j-th item (in 0-based indexing) of the set, we use bitwise OR operation \[S = s |(1<<j)\]

3. To check if the j-th item of the set is on, use the bitwise AND operation T = S&(1<<j). if T=0, it was off, else it was on.

4. TO clear/turn-off j-th item of the set, we use the bitwise AND and NOT operations. 

S = S& (~(1<<j)).

5. To toggle(flip the status of) the j-th item of the set, we use the bitwise XOR operation:

S = S^(1<<j).

6. To get the value of the least significant bit that is on (that is, the first on bit from the right), use 

T = (S&(-S)). Assuming(which is indeed the case) that negative numbers are stored as two's complements.

7. To turn on all bits in a set of size n, we use S = (1<<n)-1

I suggest you pick up a pen/pencil and figure out why these tricks/methods work.

Here are some less commonly used bit manipulation tricks:

1. (Very Important, imagine other way of checking it) Determine if S is a power of two: (111) is not a power of 2, but (100) is a power of 2. You can check it as follows:
                                                                              S&(S-1) == 0

2.  Turn off the first(from right) on bit in S. That is $(101000) -> (100000)$. You can do it as follows:
                                                                              S&(S-1)
3. Turn on the last zero in S. $(101001) -> $101011)$. This can be done as follows:
                                                                               S|(S+1)
4. Turn off the last consecutive run of ones in S. (100111) -> (100000):
                                                                                S&(S+1)
5. Turn on the last consecutive run of zeros in S. (100100)->(100111):
                                                                                S|(S-1)