0

So the challenge is to design an algorithm that PRINTS the subsets of a given set n.

Let's set n equal:

 n = {a,b,c}

On this stack overflow article there is an answer from @Piva that solves this problem using the fact that "Each number from 0 to 2^n gives a unique subset in its binary representation"

I have written a Javascript version of @Piva's code, it works well. I understand most of it except one line:

if(((i>>j) & 1) === 1)

I think I understand this line of code is shifting i bits right, adding j zeros to the beginning of i's binary representation. I also understand the bit wise & is comparing i >>j to 1 and seeing if the first bit is on from the output i >>.

But I don't understand how this operation identifies unique binary representations and why the if(((i>>j) & 1) === 1) being true means we have a unique subset of a given n.

Here is my Javascript version:

    function SubsetBuilder(set) {
        this.set = set;

    }

    SubsetBuilder.prototype.getSubsets = function () {
        var self = this;

        if (!self.set)
            return null;

        //recursive way, do next
        var getSubsetsAll = function (originalSet) {
            if (!originalSet) {
                return;
            }
        }

        var n = this.set.length;
        for(var i = 0; i < (1<<n); i++) {
            var subset = [];
            for (var j = 0; j < n; j++) {
                console.log('i:' + i + ", binary: " + i.toString(2));
                console.log('j:' + j + ", binary: " + j.toString(2));
                console.log('(i >> j):');
                console.log((i >> j));
                console.log('((i>>j) & 1):');
                console.log(((i >> j) & 1));
                if(((i>>j) & 1) === 1){ // bit j is on
                    subset.push(this.set[j]);
                }
                console.log('-------------------');
            }
            console.log(subset);
            console.log('-------------------');
        }
    }

    var set = ['a', 'b', 'c'];
    var obj = new SubsetBuilder(set);
    obj.getSubsets();
Community
  • 1
  • 1
Brian Ogden
  • 18,439
  • 10
  • 97
  • 176

1 Answers1

3

if(((i>>j) & 1) === 1) checks if the j-th bit of i is set.

To understand how this works, consider the number 5 in binary 101b. >> is just a shift (or equivalently, division by 2n) and & 1 masks out all but the least significant bit.

(101b >> 0) & 1 = (101b & 1) = 1
(101b >> 1) & 1 = ( 10b & 1) = 0
(101b >> 2) & 1 = (  1b & 1) = 1

So once wen understand how the bit-extraction works, we need to understand why bit-extraction is equivalent to subset inclusion:

Here's how we map from binary numbers 0-7 to subsets of {A,B,C}

0: 0 0 0   => {     }
1: 0 0 1   => {    A}
2: 0 1 0   => {  B  }
3: 0 1 1   => {  B A}
4: 1 0 0   => {C    }
5: 1 0 1   => {C   A}
6: 1 1 0   => {C B  }
7: 1 1 1   => {C B A}

And clearly we have listed all subsets.

Hopefully you can now see why the test for the j-th bit of i is equivalent to the inclusion of the j-th object into the ith subset.

Michael Anderson
  • 70,661
  • 7
  • 134
  • 187
  • Ok, I am getting there, I worry that it is taking me so long to grasp this though I have been writing code for almost 20 years lol. So I am getting that a bitmask is a way to "mark" subsets of set n. I am seeing now, thanks to your answer that if(((i>>j) & 1) === 1) is checking if the j-th bit of i is "ON" and i is a bitmask that marks a point, with a binary 1 where we have a unique subset. A couple things I would like to be clearer on, the operator >> in particular. I understand what 1<> j – Brian Ogden Oct 26 '15 at 02:20
  • Would I read i >> j as the following, "add j zeros to the beginning of the binary notation of i"? – Brian Ogden Oct 26 '15 at 02:22
  • Made it clearer what each of the operators is doing in the description. – Michael Anderson Oct 26 '15 at 02:27
  • Awesome answer, you the man^n lol. One last question if you could be so kind, why does i iterator 2^n-1 and not 2^n, I know that I can "build S(n) by cloning S(n-1) and adding n to the cloned sets but I am still having trouble picturing why its S(n-1) for i – Brian Ogden Oct 26 '15 at 02:39
  • Never mind, for the set {a,b,c} i is iterating 8 times, I thought it was for seven for a minute there – Brian Ogden Oct 26 '15 at 02:51