1

FOR MODERATOR:

The question for which this is a supposed duplicate of, does not address a number of issues.

  1. This question is not about how the operators work per se, but how they function in the algorithm, i.e. why those operators at that point.
  2. This question also includes the bit-wise comparison '&' operator, which the
    other question does not address at all.
  3. The central insight to the answer provided is that by assigning
    combinationsCount = 1 << listSize one turns the iterator 'i' in the loop into a bit vector, which can be tested against a particular 'j' to determine if it should be included in the sum to test.

This is a solution to a variation of the coin change problem, I think. The code works, to the best of my knowledge, but I do not understand how the last if check:

if (i & (1 << j)) {
    combinationSum += arr[j];
}

works in this algorithm (see below). I ran into it working through a tutorial. I'd really appreciate any explanation of how that portion of the code works.

UPDATE:

To be clear, I understanding WHAT the operators are doing, i.e. the bit shifting and the bit-wise addition. What I want to know is how they operate within the algorithm.

possibleCombinationSumN(arr, n) {
  if (arr.indexOf(n) >= 0) {
    return true;
  }

  if (arr[0] > n) {
    return false;
  }

  if (arr[arr.length - 1] > n) {
    arr.pop();
    return possibleCombinationSumN(arr, n);
  }

  var listSize = arr.length, combinationsCount = (1 << listSize)
  for (var i = 1; i < combinationsCount; i++) {
    var combinationSum = 0;
    for (var j = 0; j < listSize; j++) {
      if (i & (1 << j)) {
        combinationSum += arr[j];
      }
    }
    if (n === combinationSum) {
      return true;
    }
  }
  return false;
};
mpromonet
  • 11,326
  • 43
  • 62
  • 91
Ahmad Ragab
  • 1,067
  • 1
  • 12
  • 24
  • Small clarification: "bit-wise comparison '&' operator" - it is not a comparison operator, it is a bitwise "and" operator. It is very often used to extract a single bit, like it is here (as it copies bits at `1`, but zeroes the bits at `0`); in this case, it is called "masking", and the "pattern" for the extraction (`1< – Amadan Jan 20 '16 at 00:42
  • Thank you for the clarification, and now the term bit mask becomes a bit more clear. – Ahmad Ragab Jan 20 '16 at 04:35

1 Answers1

2

i serves as a bitvector (row of zeroes and ones) that turn on or off the participation of the corresponding array values in the sum.

For example, if arr has 4 elements, when i is 11, its binary representation is 0b1011; this indicates that we should sum up arr[3] + arr[1] + arr[0], and leave out arr[2].

Now - for a four-element array, i will go from 0 to 15. Why? Because 1 << arr.length is binary 0b10000 (0b1 shifted left four positions), or 16, and we loop to just under that. This gives us binary values between 0b0000 and 0b1111 - i.e. all possible combinations of four ones and zeroes. If we then sum up the corresponding array values, we will have tested all possible combinations of sums.

i & (1 << j) tests if the j-th bit is 1.

Say j is 3, and i the abovementioned 11 (0b1011). 1 << j is 0b1000; 0b1011 & 0b1000 is 0b1000, which is truthy. There is a one at position 3, and arr[3] gets to be in the combinationSum.

Say j is 2. 1 << j is 0b10; 0b1011 & 0b100 is 0b0, which is falsy. There is a zero at position 2; arr[2] does not get summed.

Amadan
  • 191,408
  • 23
  • 240
  • 301