What mathematical function does bitwise AND (&) op

问题:

A little context, I was looking at another SO post when I am trying to solve javascript problem to find all possible subsets. I am not asking about the JS challenge, but why it was there and what mathematical significance does it have?

Here is the copy paste of the code from this SO post

var arr = [1, 2, 3];

function generatePowerSet(array) {
  var result = [];
  result.push([]);

  for (var i = 1; i < Math.pow(2, array.length); i++, result.push(subset))
    for (var j = 0, subset = []; j < array.length; j++)
      if (i & Math.pow(2, j))
        subset.push(array[j]);

  return result;
}

console.log(generatePowerSet(arr));

I don't understand what is being accomplished by if (i & Math.pow(2, j)) line. The mozilla doc says that it performs AND comparison on each bits pair. Why is it relevant?

What I mean when I say relevant, for example with LEFT SHIFT, doing a << 1 multiples a by two. Its equivalent mathematical function is multiplying by two if a << b and b is 1. I don't understand what mathematical function & does in this case.

回答1:

The expression i & Math.pow(2, j) gives a non-zero value when the j^th bit in i is 1 (counting from the least significant bit, which is the 0^th bit).

This can be best explained by example. Let's say i is 10 at a certain moment; in binary: 1010. Now let j be 0. Then:

     i & Math.pow(2, j)
 ==  10 & Math.pow(2, 0)
 ==  10 & 1
 ==  0b1010 & 0b0001
 ==  0b0000

The effect of the second value (0b0001) is filtering: it filters out exactly one bit from the first value. See what happens when j is 1:

     i & Math.pow(2, j)
 ==  10 & Math.pow(2, 1)
 ==  10 & 2
 ==  0b1010 & 0b0010
 ==  0b0010

The if condition will thus be true for this value of j.

As i has two 1 bits, there will be two times that the if condition is true for that particular value of i.

回答2:

Lets look at a bitwise counter that increments by one:

 0 -> 000
 1 -> 001
 2 -> 010
 3 -> 011
 4 -> 100
 ...
 7 -> 111

As you can see if we we imagine 1 being true and 0 being false, it actually generates all possible 4 boolean combinations. So its actually perfect to generate a powerSet. We just need one counter (i) that goes over these values and then we need to turn the booleans into the arrays elements. For that we need to go over it from left to right

 for (var j = 0, subset = []; j < array.length; j++)

and check if that one boolean (bit) is checked

if (i & Math.pow(2, j))

if so we include the element at that array indexinto the result.

回答3:

& is a bitwise AND comparison. What it does it compare two numbers' binary representations, bit-by-bit.

In your example, 1, 2, and 3 are represented in binary as 01, 10, and 11. Therefore, 1 & 2 = 01 & 10 = 0. Likewise, 1 & 3 = 01 & 11 = 01 = 1.

The if (i & Math.pow(2, j)) line is doing this comparison for i & 2^j.

回答4:

That post was about generating all of the subsets of the set. As an example [1, 2, 3] set was taken.

Now let's go through that code that you have:

for (var i = 1; i < Math.pow(2, array.length); i++, result.push(subset))

The values of i loop from 1 through 2^Length_Of_Set, which in our sample is 2^3 = 8.

And here are the binary values of numbers from 1 through 8:

1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111

If we say, that each of those 3 bits represents the value from our original set, and if it is 1, then let's include it in subset. This means that 7 binary values above represent all of the possible subsets of our original set.

Logical AND operation between two numbers results in a bitwise multiplication between their binary representations:

1 & 2^0 = 001 * 001 = 001 (0*0, 0*0, 1*1)
2 & 2^0 = 010 * 001 = 000 (0*0, 1*0, 0*1)
...
7 & 2^2 = 111 * 100 = 100 (1*1, 1*0, 1*0)

So, once again going back to original post regarding subsets - first cycle produces all possible combinations of 0 and 1 with fixed length of n, which is equal to number of elements in our set.

The second cycle produces 2^k values, which are equal to:

001
010
100
...

where k is index of the element in our original set.

And this 2^k, multiplied to the combinations produced by first cycle, using & or AND operation, gives us the simple result saying if the element at index k should be included in the final subset.

回答5:

In binary, any power of two will just be a single 1 followed by zeros. Briefly:

• 2^0: 1
• 2^1: 10
• 2^2: 100

and so on.

Additionally, as you know, the power set of A is the set of all subsets of A. Conveniently, if A has n elements, then a subset of A can be represented by n bits, where each bit corresponds to an element of A. If the bit is 1, we include the element, if not, we don't.

So to get a power set, if we could just go through each number from 1 to 2^n, and create subsets accordingly. So we just need a way to generate the subset from the number we are given.

So the lines:

// get each number from 1 -> 2^n. These represent each subset.
for (var i = 1; i < Math.pow(2, array.length); i++, result.push(subset))
  // Now we need to see which elements of the original array
  // go into this subset. So we check each one individually:
  for (var j = 0, subset = []; j < array.length; j++)
    // And finally, we only put this item in the subset if
    // the bit at index we are at is 1.
    if (i & Math.pow(2, j))
      subset.push(array[j]);

The critical point being that we should only include the element if the bit at the same index is 1. So to do that, we use that bitwise operator. Now, we know that in binary, 2^j is all zeros except for a single 1 at the j'th position. So then if you bitwise AND that with i itself, the result will be all 0 if the bit in the j'th position of i is 0 (falsey), or 2^n (truthy) otherwise.

So TL;DR:

(i & Math.pow(2, j))

Is true if and only if the j'th bit of the binary representation of the number i is a 1.