CODEWITHSUNDEEP
cincrementstandardspre-increment
Thomas Baruchel
Thomas Baruchel

Reputation: 7517

Is this two-increments expression well-defined in C?

I want to iterate over integers up to some power of 2 t by skipping all integers having a specific bit set. Let m be some power of 2 (smaller than t), I want to skip all integers j such that j&m != 0. I like the following for-loop, but I wonder whether it is perfectly defined according to the standard:

for (int j=0; j < t; j += (++j) & m) {
    ...
}

The idea is:

But since there are two increments in the same expression I want to make sure it is perfectly correct.

Upvotes: 0

Views: 150

Answers (4)

Lundin
Lundin

Reputation: 214770

It is undefined behavior. The relevant parts of the standard are:

C17 6.5 §2 (expressions):

If a side effect on a scalar object is unsequenced relative to either a different side effect on the same scalar object or a value computation using the value of the same scalar object, the behavior is undefined. If there are multiple allowable orderings of the subexpressions of an expression, the behavior is undefined if such an unsequenced side effect occurs in any of the orderings.

C17 6.5.16 §3 (assignment operators):

The side effect of updating the stored value of the left operand is sequenced after the value computations of the left and right operands. The evaluations of the operands are unsequenced.

C17 6.5.16.2 §3 (compound assignment):

A compound assignment of the form E1 op= E2 is equivalent to the simple assignment expression E1 = E1 op (E2), except that the lvalue E1 is evaluated only once

Based on that:

  • Some flavour of j + ++j is UB.
    The expression j += (++j) & m is equivalent to j = j + ((++j) & m). The value computation j +... is unsequenced in relation to the side effect ++j on the same object. UB as per "side effect unsquenced relative a value computation of the same object".

  • Some flavour of j = ++j is UB.
    The evaluations of the operands of = are unsequenced: j = ... vs j + ((++j) & m) . UB as per multiple allowable orderings where an unsequenced side effect ++j occurs.

Upvotes: 1

Jonathan Leffler
Jonathan Leffler

Reputation: 754790

As has been generally noted, the expression you are trying to use has undefined behaviour because the ++ and the += are unsequenced. However, your description of what you're trying to do suggests that using j += 1 + ((j + 1) & m) should do what you require without any undefined behaviour.

#include <stdio.h>

int main(void)
{
    int m = 0x8;
    int t = 33;

    for (int j = 0; j < t; j += 1 + ((j + 1) & m))
        printf("%d\n", j);

    return 0;
}

Output:

0
1
2
3
4
5
6
7
16
17
18
19
20
21
22
23
32

I think that fits with what you describe. Because m is 8, it immediately skips values 8..15 and 24..31 which are the values in the range 0..32 that have the bit set.

Note that this only works correctly if the initial value for j does not include the bit identified by m. If you change the start from 0 to 9, you get the output 9, 18..23, 32. The code can be modified to deal with that, of course, but it is a bit tricky and exactly how to do it depends on as yet unstated requirements (what is the expected output?).

Side note: it would be helpful if your question included sample output of what you expected as output, analogous to what I've provided. Please read about how to create an MCVE (Minimal, Complete, Verifiable Example — or MRE or whatever name SO now uses) or an SSCCE (Short, Self-Contained, Correct Example — the same idea by a different name).

Upvotes: 3

dbush
dbush

Reputation: 224882

The expression j += (++j) & m invokes undefined behavior because it contains multiple unsequenced writes to j.

Rather than trying to come up with a "clever" increment, just do the increment in the for statement and perform the check inside of the loop.

for (int j=0; j < t; ++j) {
    if ((j&m) != 0) {
        // skip ahead
        j += m - 1;
        continue;
    }
    ...
}

Upvotes: 3

gulpr
gulpr

Reputation: 4608

The behaviour of this program is not defined (UB) as *(thank you Eric)*there is no sequence point between the modification and assignment are not sequenced.

Many compilers will emit a warning:

warning: unsequenced modification and access to 'j' [-Wunsequenced]
    |     for (int j=0; j < t; j += (++j) & m) {

Even if it was OK I would strongly discourage you from writing this kind of "hacky" expressions as they are very difficult to read for humans making the code very hard to understand, debug and maintain

Upvotes: 4

Related Questions