Использование различных двоичных чисел для поиска подмножеств заданного набора

Question

Таким образом, задача состоит в разработке алгоритма, который ПРИНЦИПЫ подмножеств заданного набора n.

Зададим п равна:

n = {a,b,c} 

На этой stack overflow article есть ответ от @Piva, который решает эту проблему, используя тот факт, что «Каждое число от 0 до 2^п дает уникальное подмножество в его двоичный представление "

Я написал Javascript версию кода @ Piva, она работает хорошо. Я понимаю, большинство из них, кроме одной строки:

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

Я думаю, что я понимаю, эта строка кода смещается I бит вправо, добавление J нулей в начале я в двоичном представлении. Я также понимаю, что бит & сравнивает i >> j с 1 и видит, включен ли первый бит с выхода i >>.

Но я не понимаю, как эта операция идентифицирует уникальные двоичные представления и почему истина означает, что у нас есть уникальное подмножество данного n.

Вот моя версия JavaScript:

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(); 

Answer 1

if(((i>>j) & 1) === 1) проверяет, является ли J-й бит I установлен.

Чтобы понять, как это работает, рассмотрите номер 5 в двоичном коде 101b. >> - это просто смена (или, что то же самое, деление на 2 ⁿ) и & 1 маскирует все, кроме наименее значимого.

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

Так как только вэнь понять, как работает бит добыча, мы должны понять, почему бита-экстракция эквивалентна подмножество включения:

Вот как карта из двоичных чисел 0-7 для подмножеств { 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} 

И, очевидно, мы перечислили все подмножества.

Надеюсь, теперь вы можете увидеть, почему тест для j-го бита i эквивалентен включению j-го объекта в i-ю подмножество.