When does N & (1<

Question

I've recently been studying complete search with generating subsets using bit operations, so I've stumbled upon the following code:

for(int b = 0; b < (1<<n); b++) {
    vector<int> subset;
    for(int i = 0; i < n; i++) {
        if( b&(1<<i)) subset.push_back(i);
    }
    //use subset here
}

This code is used to find all subsets of a set of n elements. I'm confused by the part

b&(1<<i)

Which is clearly false if the i-th bit of b is 0, but I don't see why it'd be true if the i-th bit of b is true, I mean wouldn't the result just be 2 to the power of i (which as it doesn't equal one i.e. true, should return false)?

changes: Beside that, I noticed now that I know that any number different from zero is considered true, that N & (1<<x) == true is true if x is 0 and N is odd, or x>0 and N is even, due to the preference of == over & , so N & (1<<x) == true resolves to N & ( (1<<x) == true )

Though I do know I can just put ( b & ( 1<> i to get the value of the i-th bit of b, it just doesn't seem to me that that part was missed in the book I was studying from. — Martin Dinev, May 23 '17 at 14:47
Here is a nice [list](http://en.cppreference.com/w/cpp/language/implicit_conversion#Boolean_conversions) which types can be implicitly converted to `bool`. — Rakete1111, May 23 '17 at 14:48
Possible duplicate of [In c, in bool, true == 1 and false == 0?](https://stackoverflow.com/questions/40009029/in-c-in-bool-true-1-and-false-0) — phuclv, May 23 '17 at 15:00
The question in the title is **different from** the question in the code. When you compare a numeric expression with `true`, `true` gets promoted to `int` with the value 1, and the comparison succeeds only if the value of the expression is also 1. When you use a numeric expression in an `if()` statement its value is contextually converted to `bool`, and any non-zero value will be converted to `true`. — Pete Becker, May 23 '17 at 15:27

score 8 · Accepted Answer · answered May 23 '17 at 14:46

8

You have a small misunderstanding...

which as it doesn't equal one i.e. true, should return false )

The truth is: only 0 is converted to false while all other numbers become true.

answered May 23 '17 at 14:46

463035818_is_not_an_ai

109,796
11
89
185

score 3 · Answer 2 · answered May 23 '17 at 14:47

Which is clearly false if the i-th bit of b is 0, but I don't see why it'd be true if the i-th bit of b is true, I mean wouldn't the result just be 2 to the power of i (which as it doesn't equal one i.e. true, should return false)?

Your mistake here is not that 1 is true and all others is false. In C++ 0 is false and all other values are true.

score 3 · Answer 3 · answered May 23 '17 at 14:48

Recall that when a numeric expression is used in C or C++ in places where a logical expression is needed, such as ifs or whiles, the expression result is implicitly compared to zero. Expressions returning zero mean "false", while expressions returning non-zero mean "true". They do not need to return 1^*.

Now recall that 1 << i constructs a number with the binary representation that has a single 1 in i-th position. Performing an & of a number b with such number yields zero when b-th bit at position i is zero. When bs bit in position i is one, the expression produces a non-zero value, which is interpreted as "true" by the if statement.

^* When C or C++ evaluates a logical expression, such as ! or &&, it produces 1, not an arbitrary non-zero number.

score 0 · Answer 4 · answered May 23 '17 at 18:24

This is a pretty common confusion, you mixed 2 things:

boolean to integer conversion: true is converted to 1, false is converted to 0
integer to boolean conversion: 0 converted to false, anything else is converted to true.

so when you use expression which result is int in if or while or any other statement that requires boolean value you implicitly convert it to bool hence second case. This code:

if( b&(1<<i)) subset.push_back(i);

is logically the same as:

bool flag = b&(1<<i);
if( flag ) subset.push_back(i);

When does N & (1<

4 Answers4