Bit Manipulation tips and tricks

Prashant Mishra - Sep 17 - - Dev Community

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)
Enter fullscreen mode Exit fullscreen mode

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


Check if ithi^{th} bit is set or not

Here, ithi^{th} bit is ithi^{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 ithi^{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 ithi^{th} but must be set.

example:
13213_2 =1101, if i = 2, check if ithi^th bit is set or not
1<<i = 1<<2 = 100
1101 & 100 = 0100, hence if the ithi^{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 ithi^{th} bit in X is unset else set


Set ithi^{th} bit in a number X

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

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


Unset or clear ithi^{th} bit in number X

This is very similar to setting ithi^{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 = 13213_2 = 1101, i =2;
1<< i = 0100 -> ~(0100) = 1011
finally
1101 & (1011) = 1001 = number with ithi^{th} bit unset or clear


Toggle the ithi^{th} bit of number X

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

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

i.e toggling can be done using Exor

X ^ (1<<i) = number with ithi^{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:

X X-1
13 = 1101110\color{red}1 12= 1100110\color{green}0
34= 1000101000\color{red}1 0 33= 1000011000\color{green}01

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 = 0100_{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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Terabox Video Player