Clever Geek Handbook

When is N & (1 << x) == true?

I was recently researching full search with subsets generation using bit operations, so I came across 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 elements n

. The part confuses me

b&(1<<i)

This is clearly not true if the i-th bit b

is equal 0

, but I don't understand why it would be true

if the i-th bit b

is equal true

, I mean that the result should not be 2

up to a degree i

(which, since it is not equal to one, then is true, should return false

)?

edit : Also, I noticed that I now know that any number other than zero is considered true

to N & (1<<x) == true

be true if it x

is 0

both n

odd or x>0

and n

even due to the preference ==

over &

, so it N & (1<<x) == true

resolves toN & ( (1<<x) == true )

+3


source share


4 answers


You have a little misunderstanding ...

which is not equal to one, that is, true should return false)



The truth is this: only 0

converted to false

, and all other numbers become true

.

+7


source


This is clearly not true if the i-th bit b

is equal 0

, but I do not understand why it would be true

if the i-th bit b

is equal true

, I mean that the result will not only be 2

up to the degree i

(which, since it is not equal to one, that is true, should return false

)?



Your mistake here is not what 1

is true

, but everyone else false

. In C ++ 0

there is false

, and all other values ​​are true

.

+3


source


Recall that when a numeric expression is used in C or C ++ where a boolean expression is required, such as if

or while

s, the result of the expression is implicitly compared to zero. Expressions that return zero mean false, and expressions that return nonzero mean true. They don't need to return 1

* .

Now, recall that it 1 << i

builds a binary number that has one 1

at the i-th position. Doing a &

number b

with such a number yields zero when the b

-th bit at position i

is zero. When a bit b

in a position i

is one, the expression produces a nonzero value, which is interpreted as "true" by the operator if

.

* When C or C ++ evaluates a Boolean expression like !

or &&

, it produces 1

, not an arbitrary non-zero number.

+3


source


This is a fairly common confusion, you have mixed 2 things:

  • boolean to integer conversion: true

    converted to 1, false

    converted to 0
  • integer to boolean conversion: 0 is converted to false

    , everything else is converted to true

    .

so when you use an expression whose result is int

in if

or while

, or any other operator that requires a boolean value, you are implicitly converting it to bool

hence the second case. This code:

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

logically the same as:

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


source






More articles:


All Articles