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 bit is set or not
Here,
bit is
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
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
but must be set.
example:
=1101, if i = 2, check if
bit is set or not
1<<i = 1<<2 = 100
1101 & 100 = 0100, hence if the
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 bit in X is unset else set
Set bit in a number X
We can use or operation:
(X | (1<<i))
= value with
bit set
Example : X =
= 1001, i = 2
We know, 1<<i
= 100
i.e. 1001 | 100 = 1101
(
bit is set)
Unset or clear bit in number X
This is very similar to setting
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 =
= 1101, i =2;
1<< i = 0100 -> ~(0100) = 1011
finally
1101 & (1011) = 1001 = number with
bit unset or clear
Toggle the bit of number X
Toggle means if the bit is 0 make it 1, else if bit is 1 make it 0
What can we use here? : ^ (exor) operator, since 1 ^ 1 = 0, 0 ^ 1 = 1;
meaning if
bit is 1 exored with 1 will give 0, else if
bit is 0 exored with 1 will give 1.
i.e toggling can be done using Exor
X ^ (1<<i) = number with 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 = | 12= |
34= | 33= |
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 =
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;
}
}