2

I have a function (written by someone else) which builds combination based on a set of components. Somehow, it involves bitwise shift operations to do so, but I am having difficulty in understanding it. The code is shown below:

// Declarations in the header file. vector<set<Component*, compareComponentIDs>> allScenarios; // The function. void System::buildAllScenarios() { int x, y; for (x=1; x < (1 << (int)components.size()); x++){ set<Componenet*, compareComponentIDs> curScenario; for(y=0; y < (int)components.size(); y++){ if ((x >> y) & 1){ curScenario.insert(components[y]); } } allScenarios.push_back(curScenario); } return; }

Let's say the number of component is 10. Then, I think the first for loop will loop through 20 times, because bit wise shift left will multiply the number of component by 2. The second component will loop through 10 times, because there is no special operation. I have no clue what the if statement is evaluating.

Having this information, my questions are:

  1. How does the if statement inside of the second for loop work? What does it do?
  2. Why does the first for loop will iterate twice more than the number of components.

Any help would be appreciated.

Improve this question
1
  • 2
    This code builds combinations, not permutations. Commented Jul 6, 2014 at 17:16

4 Answers 4

Reset to default
1

You have n possible components. In a scenario, each component is in or not (2 values). Menaning that you have 2^n potential scenarios. For example, with 3 components, you have 2*2*2=8 possibilities.

The first binary shift by n is equivalent to mutliplying by 2^n (see also iso std section 5.8). So the outer loop loops through each scenario. If you write each number in binary, you would write it on n bits, each representing a component. Ex: 

0: 000 no component 1: 001 first component in 2: 010 second component in 3: 011 first and second component in, etc...

The inner loop, decodes the number of the scenario according to this logic. Shifting right by y bits mean making the bit y the last bit. x & 1 means looking only at the last bit. It lloks at the bit that corresponds to each component : if it's 0 (component not in) or 1 (component in). In this latter case, it inserts the component in a set.

Very clever and efficient algorithm, as long as there are less components than bits in an int. In order to avoid undefined behaviour related to the sign bit, if you have sizeof(int)*8 components, I'd advise to use unsigned int rather than int.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

The first loop will actually loop 1*2^10-1 times since it is the 1 that is getting shifted and not the 10. That comes out to be 1023. (x starts at 1, not 0)

The second loop will loop will loop 10 times.

The line 

curScenario.insert(components[y]);

will be run as many times as there are bits set in x. So if x is 100101, the line will be run 3 times.

I'll edit this when I figure out exactly how this does what you want it to.

Improve this answer

Comments

1

  1. The statement is called a bitwise AND, and checks corresponding bits in the 2 operands, evaluating True if both are 1.

  2. Because bit-shifting by 1 space (<< 1) is equivalent to multiplying by 2 (shifting in the decimal system would equate to multiplying by 10, for example).

Also, if I may: this is code smell to me - someone is trying to be smart with bitwise operations, not realizing that compilers are doing all the optimization heavy lifting here. Unless programming for very specific hardware, like DSPs (which would be done in C), the performance gains (if any) fall flat when looking at the lost readability.

Improve this answer

Comments

0

How does the if statement inside of the second for loop work? What does it do?

  • x >> y shifts bits of x, y places to the right.

  • & is the bitwise and operator. So (x >> y) & 1 will result in 0 if the result of (x >> y) is even and 1 if the result is odd.

Why does the first for loop will iterate twice more than the number of components?

  • It's not actually twice more, it's 2^components.size() times. 1 << (int)components.size() will shift the bits of the left side (i.e., 1) components.size() places to the left. This is equivalent as saying 2^(components.size()). A result which is relevant to what your code actually does, which is to compute the power set of your scenarios.
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.