🙏

জয়  শ্রী  রাম

🕉

---

A Bitmask is data that is used for bitwise operations, particularly in a bit field. Using a bitmask, multiple bits in a byte can be set either turned on (i.e, 1), off (i.e, 0) or inverted from on to off (or vice versa) in a single bitwise operation.

Let's discuss some bit manipulation operations often done on bitmasks to solve different problems:

Setting A Bit

Setting a bit means setting that bit to 1. The opposite operation is called resetting a bit or clearing a bit which involves making a bit zero.
The bit that we set is always one irrespective of whether it was one or zero before. No changes occur to any other bits. How can we achieve this ? Remember that in OR operation 0 | 1 = 1 and 1 | 1 = 1. We get 1 on a bitwise OR for bot 0 and 1. So an easy and effective solution would be to take a binary number which has 1 at the bit we want to set, and 0 in all other bits, and then OR it with the number we are trying to operate on. So if we want to set the 0 at 3rd bit from right (zero based index) of 1110111 then we would need to do an OR with 0001000.
e can get the number with which we need to do OR as follows:
Remember that 1 is represented as 00000001. If you want to set, say, bit at position 3 from right, then K should be equal to 00001000. We can get 00001000 by shifting 1 three positions towards left. 00001000 = 00000001 << 3 = 1 << 3.
It is very important that we understand the above concept very well. The rest of the discussion will be based on this discussion.
Let's look at the code how to set ith bit from right:

public int setBit(int inputNumber, int bitPositionFromLeft) {
    int binaryNumberWithOneAtTheRequiredPositionAndZeroEverywhereElse = 1 << bitPositionFromLeft;
    return inputNumber | binaryNumberWithOneAtTheRequiredPositionAndZeroEverywhereElse;
}

Notice that (0001)₂ = (2⁰)₁₀ = (1)₁₀, (0010)₂ = (2¹)₁₀ = (2)₁₀, (0100)₂ = (2²)₁₀ = (4)₁₀ and so on. ()₂ indicates number in binary and ()₁₀ indicates number in decimal.

Clearing/Resetting A Bit:

Clearing or Resetting a bit will make that bit equal to 0. So, if we have understood the core of the concept described above, we would quickly know that we need an operation that gives you 0 for both 1 and 0. AND with Zero fits perfect here because 0 & 0 = 0 and 1 & 0 = 0.

So if we want to reset 3^rd bit from left (0 based index) we would need 11110111. How can we get this ? Look that it is complement of 00001000. 11110111 = ~00001000. So we can just compute 00001000 and flip all the bits.

public int resetBit(int inputNumber, int bitPositionFromLeft) {
    int binaryNumberWithOneAtTheRequiredPositionAndZeroEverywhereElse = 1 << bitPositionFromLeft;
    return inputNumber & ~binaryNumberWithOneAtTheRequiredPositionAndZeroEverywhereElse;
}

Get Bit:

What Get Bit does is returns if the it at i^th position is 0 or 1.
We know ANDing a number with 1 gives back the same number, since 0 & 1 = 1 and 1 & 1 = 1.
What we can do is: if we are interested in knowing what i^th is, we can form a number that has 1 at i^th bit and 0 in all other bits. Now, if the number has 0 in i^th bit then the number AND one will give you ZERO. If the i^th bit is 1 then we will get a non-Zero number.

public int getBit(int inputNumber, int i) {
    int k = 1 << i;
    return (inputNumber & k == 0) ? 0 : 1;
}

Flipping Bit

Here we are interested in flipping i^th bit (from right) from 0 to 1 or vice versa.
So, for the i^th bit we are interested in finding an operation either with 0 or 1 that would give us the flipped bit.
So, what we are trying to accomplish is expressed in below two expressions:
0 < some operation > < either 0 or 1 > = 1
1 < some operation > < either 0 or 1 > = 0
Or, more explicitly,
0 < some operation > 0 = 1
and
1 < some operation > 0 = 0

OR,
0 < some operation > 1 = 1
and,
1 < some operation > 1 = 0

We see that the expressions 0 < some operation > 1 = 1, and, 1 < some operation > 1 = 0 holds true for XOR.
Since, 0 XOR 1 = 1 and 1 XOR 1 = 0.

We also know that, XOR'ing a number with 0 returns the same number since 0 XOR 0 = 0 and 1 XOR 0 = 1.
So to flip i^th bit we should use a number that has 1 at the i^th bit and 0 in all other bits for XOR'ing.

In Java, we use ^ for XOR.

public int flip(int inputNumber, int i) {
    int k = 1 << i;
    return inputNumber ^ k;
}

Flipping All Bits

Flipping all bits changes all 1s to 0 and all 0s to 1 in a binary number. We achieve this by ~ sign.
num = ~num flips all bits of variable num.

ARITHMETIC Right Shift (>>) vs. LOGICAL Right Shift (>>>)

>>

In most common cases we use ARITHMETIC Right Shift or >>.
>> does exact opposite of <<
>> shifts bits towards right. Doing >> each time is equivalent to dividing by 2. Which means, M >> N always gives you M / 2^N. M can be positive or negative. M > 0 or M >= 0.
According to the discussion above if we do (-75) >> 1, we should get floor((-75) / 2¹) = floor(-37.5) = -38.
Now let's see if this is what actually happens when we do >> operation:
(-75)₁₀ = (10110101)₂
Please note that the 1 in the Most Significant Digit (the first 1 in 10110101) is sign bit. It is 1 because it is a negative number. It would have been 0 if it were a positive number.
(..) is used to indicate a sign bit.

(1)   0    1    1    0    1    0    1
  \    \    \    \    \    \    \
   \    \    \    \    \    \    \
    \    \    \    \    \    \    \
     \    \    \    \    \    \    \ 
     _\|  _\|  _\|  _\|  _\|  _\|  _\|  
(1)    1    0    1    1    0    1    0    
    

So what we got is 11011010 which is indeed -38 since (11011010)₂ = (-38)₁₀

It is important to note that if we right shift N times i.e, if we do (>> N) operation the first N bits (from left to right) will be the bit equal to the sign bit, i.e, for negative numbers we would have N trailing 1s and for positive numbers we'd have N trailing 0s. Just do the shifting operation shown in above diagram quite a few time (i.e, >> 2, then >> 3 and so on) and see yourself how the sign bit propagates.

>>>

Now let's discuss about LOGICAL Right Shift or >>>. >>> does not care about the sign bit. Irrespective of whether we are doing the operation on positive or negative number, >>> always puts 0 in the trailing bits after shifting. So you always get a positive number as the outcome of the >>> operative even if you do the operation on a negative number. Let's see logical right shift operator in action.
Let's do (-75) >>> 1 and see what we get.

 1    0    1    1    0    1    0    1
  \    \    \    \    \    \    \
   \    \    \    \    \    \    \
    \    \    \    \    \    \    \
     \    \    \    \    \    \    \ 
     _\|  _\|  _\|  _\|  _\|  _\|  _\|  
 0     1    0    1    1    0    1    0 

(-75)₂ >>> 1 = (10110101)₂ >>> 1 = (01011010)₂ = (90)₁₀
So a logical right shift of -75 gives positive 90.

Relation between >>, << and division, multiplication

(0001)² = (2⁰)₁₀ = 1₁₀
(0010)₂ = (2¹)₁₀ = 2₁₀
(0100)₂ = (2²)₁₀ = 4₁₀
(1000)₂ = (2³)₁₀ = 8₁₀

From above we can say << does multiplication by 2.

(1000)² = (2³)₁₀ = 8₁₀
(0100)₂ = (2²)₁₀ = 4₁₀
(0010)₂ = (2¹)₁₀ = 2₁₀
(0001)₂ = (2⁰)₁₀ = 1₁₀

From above we can say >> does operation "divide by 2".

Different compilers often optimize division and multiplication by 2 operations by replacing them by right and/or left shift operation. While coding you should do this kind of optimizations as well, if you don't already.

Two's Complement

Computer stores numbers in bits, which means either 0 or 1. So, basically computers store numbers in binary number format. But there is difference between how computers store positive and negative numbers. Computers store positive numbers as itself (binary representation for that number, like computers store 2 as 00000010). But how it stores negative numbers is very specific. Computers store negative numbers as TWO'S COMPLEMENT. Basically, computers store both positive and negative numbers in TWO's COMPLEMENT representation, its just that the two's complement for the positive numbers are the same as the binary representation of the positive number. For example, for +2 the binary representation is 00000010 and so is its two's complement representation.

Two's complement is a mathematical operation on binary numbers. It is used in computing as a method of signed number representation.

The two's complement of an N-bit number (EXCLUDING the sign bit) is defined as its complement with respect to 2^N. For instance, for the four-bit number (EXCLUDING sign bit included). 0010, the two's complement is 0110, because 0010 + 0110 = 1000.

Please note that, since we are excluding the sign bit of the number we are doing two's complement on, the number always becomes a positive number while doing two's complement, irrespective of its sign. So Two Complement is always done on positive numbers, effectively.







Two's complement is the most common method of representing signed integers on computers. In this scheme, if the binary number 010₂ encodes the signed integer 2₁₀, then its two's complement, 110₂, encodes the inverse: −2₁₀. In other words, to reverse the sign of integers, except zero, in this scheme, you can take the two's complement of its binary representation.

How is negative number represented? Say we need to represent negative number -K (where K > 0) then compute two's complement of K and then put 1 in the sign bit to indicate that it is a negative number .
For example, say we need to represent -2 and we are representing numbers in four-bits representation.
(2)₁₀ = (0010)₂
When we exclude the sign bit it becomes 010, and number of bit becomes one less, i.e, 3.
Two's Complement of 2 = 2^N - 2 = 2³ - 2 = 8 - 2 = (6)₁₀ = (0110)₂
Putting 1 in the sign it becomes 1110
Therefore, (-2)₁₀ = (1110)₂ when a number is represented as 4-bits binary numbers.

Positive Numbers |  Negative Numbers
--------------------------------------
 Decimal| Binary | Decimal | Binary
    1	| 0 001  |  -7     | 1 001
    2	| 0 010  |  -6     | 1 010
    3	| 0 011  |  -5     | 1 011
    4	| 0 100  |  -4     | 1 100
    5	| 0 101  |  -3     | 1 101
    6	| 0 110  |  -2     | 1 110
    7	| 0 111  |  -1     | 1 111
         

Notice that the absolute values of the integers on the left and right always sums up to 2^N, where N = number of bits excluding sign bit = 4 - 1 = 3. The binary values on the left and right sides are identical except for the sign bit because the negative counterpart of a number K = (2^N - K) with 1 in the sign bit.

It is important to note that the two's complement is dependent on the number of bits we re using to represent a number. If N is the number of bits we are using the two's complement of a positive number would change depending on the value of N. Just remember that two's Complement of a positive number K = s^N - K. So it definitely changes because value of 2^N would change if value of N changes.

Problem Statement:

Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution:

Algorithm:

1. Generate all possible binary bitmasks of length n.
   If n = 3 then this would mean generating:
   000
   001
   010
   011
   100
   101
   110
   111
   
2. Map a subset to each bitmask: 1 on the ith position in bitmask means the presence of nums[i] in the subset, and 0 means its absence.
3. Return output list.

#1

Java code:


Login to Access Content




Python code:


Login to Access Content

#2

Java code:


Login to Access Content




Python code:


Login to Access Content




The above two implementations are a very powerful approach and can be reused in a lot of other problems to solve. -->

Instructor: