Bit Manipulation tips and tricks

Swap two numbers without using the temp variable

a = a^b
b = a^b  = (a^b)^b = a ( since b^b is 0) 
a = a^b = (a^b)^a = b  (since a^a is 0)

This way we can swap two numbers without using the temp variable

Check if $i^{th}$ bit is set or not

Here, $i^{th}$ bit is $i^{th}$ bit from the end
Using left shift:

what is 1 << i => left shift 1 two times
so, it will become 100 ( 1st shift of 1: 10 2nd shift of 10 will be 100)

So, it we have to check if $i^{th}$ bit of X is set or not
We can do: if((X & (1<<i))!=0) it will mean that the resultant number is non zero and hence $i^{th}$ but must be set.

example:
$13_2$ =1101, if i = 2, check if $i^th$ bit is set or not
1<<i = 1<<2 = 100
1101 & 100 = 0100, hence if the $i^{th}$ bit in 13 is set then only it will give non-zero value when bit-wise and is performed between 13 and (1<<i) else it will give 0.
Using right shift:

X>>i&1 ==1 ? 1:0

This means right shift X by i times and do bit-wise-and operation on the value with 1, if it is 0 then $i^{th}$ bit in X is unset else set

Set $i^{th}$ bit in a number X

We can use or operation:
(X | (1<<i)) = value with $i^{th}$ bit set

Example : X = $9_2$ = 1001, i = 2
We know, 1<<i = 100
i.e. 1001 | 100 = 1101 ( $i^{th}$ bit is set)

Unset or clear $i^{th}$ bit in number X

This is very similar to setting $i^{th}$ bit.
We just have to perform & (and) operation on ith bit with 0 to make it 0, but we have to make sure that the rest of the bits are unaffected.

X & (~(1<<i)) = Number with ith bit unset or clear

Example :
X = $13_2$ = 1101, i =2;
1<< i = 0100 -> ~(0100) = 1011
finally
1101 & (1011) = 1001 = number with $i^{th}$ bit unset or clear

Toggle the $i^{th}$ bit of number X

Toggle means if the $i^{th}$ bit is 0 make it 1, else if $i^{th}$ bit is 1 make it 0

What can we use here? : ^ (exor) operator, since 1 ^ 1 = 0, 0 ^ 1 = 1;
meaning if $i^{th}$ bit is 1 exored with 1 will give 0, else if $i^{th}$ bit is 0 exored with 1 will give 1.

i.e toggling can be done using Exor

X ^ (1<<i) = number with $i^{th}$ bit toggled(i.e. 1 if earlier was 0 else vice versa)

Example:
toggle 2 bit of 13
13 = 1101
(1<<2) = 100
1101 ^ 100 = 1001

Similarly,
toggle 1 bit of 13
(1<<1) = 10
1101 ^ 10 = 1111

Remove or clear or unset the last set bit (rightmost)

example:
13 = 1101, last set bit is at index 0 (from right)
after unsetting the last set bit it will be: 1100

This can be done by X&(X-1):
example:

Observation: the rightmost set bit in X is set to 0 in X-1 and all the other bits after that are set to 1 in X-1.

Hence when we do X&(X-1) we will set the rightmost bit in X
Example:
13 & 12 = 1101 & 1100 = 1100
34 & 33 = 100010 & 100001 = 100000

Check if number X is the power of 2 or not

The binary representation of any number which is also a power of 2 will have only 1 set bit.
Hence if X&(X-1) ==0 then X is the power of 2 else it is not.
Since X & (X-1) will reset the rightmost bit in X, and if X is the power of 2 then it will become 0.

Example:

16 = 10000
15 = 01111
16&15 = 0000 = $0_{10}$

Count the number of set bits in X

This can be done using plain brute force (count number of 1 in the binary value of X)
Example: 13 =1101 -> ans = 3;
problem

class Solution {
    public int hammingWeight(int n) {
        int count  =0;
        while(n!=0){
            if(n%2==1) count++;
            n  =n/2;
        }
        return count;
    }
}

An optimal approach using a bitwise operator( which is faster than arithmetic operators):

class Solution {
    public int hammingWeight(int n) {
        //when we do a right shift the rightmost bit is removed 
        //If we perform & operation on n with 1 it will only 
        //give 1 if the last bit of n is 1 else it will give 0
        int count = 0;
        while(n!=0){
            count+= n&1; // if the number is odd then the rightmost bit will always be 1 eg. 13 = 1101 or 5 = 101, 7 = 111. etc
            n = n>>1; // right shift or dividing by 2 
        }
        return count;
    }
}

Another approach:
We know n&(n-1) will make the rightmost set(1) bit to 0.
keeping the above logic in mind, we can count how many times we are allowed to reset the rightmost bit before the number n becomes 0. Finally, the count will have the no. of set bits in the given number n.

TC : O(31) (max bit length)

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while(n!=0){
            n = n&(n-1);
            count++;
        }
        return count;
    }
}