0:00

Before writing down the actual quote, or the resulting algorithm,

let's discuss the following important implementation remark.

Recall that in our code, we are going to iterate

through all subsets of our n nodes, right.

And at this point, it is important to discuss how we are going to do this,

right?

So once again, our goal is to iterate through all possible subsets.

So first of all, the number of such subsets is actually 2 to the n.

Recall that when we have a set of size n,

it can be actually specified just by n 0s and 1s, right?

So we can write down, we can array just the sequence like this.

And if we have n elements, say let's start them with 0,

0, 1, 2 and so on, and n- 1.

So any subset can be specified just with a 0, 1 array.

So for example, an array like this contains elements 1,

2 and so on, probably n- 1.

But does not contain the element 0,

because the corresponding cell here is equal to 0, right?

So just that each cell actually indicates whether

the corresponding element appears in our set or not.

And since there are exactly two choices for each cell, so either 0 or

1, the number of subsets is 2 to the n, right?

On the other hand, such a binary representation can be

considered as a binary representation of some integer, okay?

So there is actually a one-to-one correspondence

between all subsets of the set of size n.

Of the set consisting of element 0, 1, 2, and so on, n- 1.

And all binary representations of numbers from 0 to 2 to the n- 1, namely.

So to get this correspondence, we can do the following.

So to get from number k the corresponding set,

we write down the number k in binary.

So we're writing down something like this, it is 0101101.

So recall that this is the least significant bit, and

this is the most significant bit.

And then we treat this sequence of 0s and 1s as, no.

These 0s and 1s as indicators of whether

the corresponding element is present in our set or not.

So for example, this corresponds,

recall that this the least significant bit, and its index is 0.

That the index of this element is 0, the index of this elements is 1,

the index of this element is 2, and so on.

So, what's written here is a set that contains,

that contains elements 0, 2, 3, 4 and 6,

but does not contain elements 5 and 1, right?

Let me also illustrate this on an example, so I assume that n = 3, okay?

So we are considering all subsets of the set

consisting of 3 elements, 0, 1 and 2, okay?

Then if we write down the value of 0 in binary, we get 000, okay?

So assume that we always consider sequences of 0s and

1s, of lengths exactly 3, okay, of length n.

So we don't have just one 0, we have n 0s.

So we always append leading 0s, so that the length is equal to 3.

Now this corresponds just to the empty set, right,

just because there are only 0s here.

Then we can see the 1, in binary it is 001, right?

And this corresponds to the set consisting of a single element, 0, okay?

Once again, recall that when we write down this bit, so

this bit can correspond to the position 0.

This bit corresponds to the position 1, and

this bit corresponds to the position 2.

So we said, we number bit positions from right to left, right?

So this is the least significant bit, this is the most significant bit, okay?

Now if we consider, for example, the value 5, when k is equal to 5.

In binary, it is represented as 101, because it is just 1 plus 4, right?

And this corresponds to the fact that 0 is taken, and 2 is taken, but 1 is nothing.

So this corresponds to the subset {0,2}.

So when this is convenient, because in programming languages,

usually working with integers is particularly easy.

So it is convenient, instead of working with sets, to work with integers.

And we've just established this nice one-to-one correspondence

between integers in the range from 0 to 2 to the n- 1.

And all subsets of size, not all subsets, of a set of a size n, okay?

Now recall that we do not only need to iterate through all subsets.

But we only need to, we also, I'm sorry,

we also need to figure out how to build forms that follow an operation.

When we have a subset S,

we need to find out how to subtract some element j from it.

Namely, if we just have an integer k, which represents the set S,

we need to somehow find the representation of the set S minus, okay?

So, I assume that S represent the set,

that k represents the set S, so what does it actually mean?

It means that if we write, If we write our number k in binary,

so here we have j, and so on, and so on, n.

So we write it in binary somehow, it looks like this, and so on.

Here we have 1, and here we have something.

So what we need to do, so this is k in binary, to subtract j from the set S,

we actually need to replace this 1 with 0, right?

So we need to flip the j-th bit of the number k.

So we need to figure out how to flip the j-th bit of the given integer k,

okay, so this is what we've just realized, okay?

But when we have a number, if we have a number in binary, comes in like this this.

So it has 1 in j-th position, and we would like to flip it.

This is actually the same as computing the bitwise parity, or

the bitwise OR, XOR, with the following number.

So it has 0 everywhere except for the j-th position.

8:38

So in order to flip the j-th bit,

we need to compute a bitwise XOR of k and 2 to the j.

And finally, this is how it can be done.

So in popular languages like C++, Java, or Python,

to flip the j-th bit of k from 0 to 1,

we need to compute the following strange thing.

So let me try to parse what is written here.

So I shift, this is called binary shift to the left, so

this can be understood as follows.

So we take the number 1, and we shift it to the left by j positions,

so what we get is actually a number like this.

So it is the j-th position, and here we have j 0s, okay,

and then so this operator is called the binary shift.

And once again, if you can just compute 1, and

apply this operator to j, then it actually computes a number 2 to the j.

For example, you can check what is going to be printed

if you print something like 1 to the, 2 to the 10.

So it is going to print 1,024, because this is,

my analysis says 2 to the power of 10, okay?

And then finally, this sign, compute the bitwise parity.

So this separation, k, and then bitwise XOR with 1,

shifted through j positions to the left.

This exactly corresponds, exactly the decimal

representation of the set S where the element j is removed.

Again, we are now ready, completely ready to write down the code.

And this is exactly what we're going to do in the next video.