boolean operator in for loop in c++

Question

I know how to program in Java, but I am trying to learn C++. I am trying to do some contest in where they present you an algorithm and you try to solve it using any language you want.

I was stuck on one algorithm and searching I found this piece of code that might be helpful for me but I am a little confused in the last part of the statement in the for loop

  int N,K;
  scanf("%d %d",&N,&K);   

  for(int j = 0,x;j<N;++j){
          scanf("%d",&x);
          x = N+1-x;

          for(int idx = x-1;idx>0;idx -= (idx & -idx)) aux2 += T[idx];

I am confused in the part:

idx -= (idx & -idx)

I know that "-=" is equivalent to:

idx = idx - (idx & -idx)

and I know that "&" is the logic operation AND but I don't know how can you operate an integer with a boolean.. for a java guy like me this is a little bit confusing.

I was wondering if someone could help me here.

Answer 1

The expression idx -= (idx & -idx) sets the lowest bit in idx whose value is 1 to 0.

For example, 10001010010 ==> 10001010000.

So the number of iterations in the loop above will be equal to the number of 1s in idx.

BTW, a simpler way to perform this operation is with idx &= idx-1.

The SWAR Algorithm is considered to be the most efficient way to count the number of 1s.

Answer 2

bitwise operators operate, well on each bit of their arguments. In particular, & applies the AND operator , so an example (for 4bit arguments) would be

  0101
& 1011
------
  0001

Answer 3

you're confusing bitwise operators with boolean operators.

• operator & is the binary (aka bitwise) AND operator. In the case of integers, it does an AND operation on each and every bit. So for example: 1 & 2 is equal 0.
• operator && is the boolean and operator (aka logical AND). In C++ it takes two values (not only bool, ints will do too), and checks if both of them are true (in the case of integers - not equal to 0).

In C++, idx && -idx would be legal too, and would be equal true if idx wasn't 0, but it wouldn't do the same as in the current version.