Clever Geek Handbook

Cryptic for-loop update operators

The code I have has the following loops:

for (i = A[x]; i < N; i = i | (i + 1))

and

for (i = A[x]; i >= 0; i = (i & (i + 1)) -1 )

I don't really understand these update instructions. Are these clever ways of doing something trivial?

+3


source to share


2 answers


When the code confuses you, experiment with it.

$ cat test.c
#include <stdio.h>

int main(void)
{
  for (unsigned int i = 0; i < 256; i = i | (i + 1))
    printf(" %04x", i);
  putchar('\n');
  return 0;
}
$ gcc -std=c99 test.c
$ ./a.out
0000 0001 0003 0007 000f 001f 003f 007f 00ff


So, the first expression that confuses you ( i = i | (i + 1)

) creates sequential bitmasks from the bottom bit up.

You can use the same technique to determine what the second expression does.

+6


source


For the first, let's check what it does if it is i

initially zero:

The first iteration i

is zero, binary 0000

. Then you end up with an update expression, which performs a bitwise OR between zero and zero plus one:, 0000 | 0001

resulting in a value 1

.

Second iteration 0001

and its direction 2

(binary 0010

), which results in 3

( 0011

).



Third iteration 0011

(i.e. value 3

) which you or with 0100

(value 4

which is 3+1

), which results in 0111

(i.e. value 7

).

It continues as follows, setting all bits from the least significant bit to the maximum value.

+2


source






More articles:


All Articles