constexpr with operator|=

Question

I tried to write a function, which returns an integer with only the highest bit of the input set, using a C++0x constexpr.

constexpr inline uint64_t
get_highest_bit(uint64_t p)
{
  return 
     (p|=(p>>1)),
     (p|=(p>>2)),
     (p|=(p>>4)),
     (p|=(p>>8)),
     (p|=(p>>16)),
     (p|=(p>>32)),
     (p-(p>>1));
}

This gives a compile-time failure using gcc 4.6.1.

error: expression ‘(p <unknown operator> ((p >> 1) | p))’ is not a constant-expression

Note that it works without the constexpr keyword.

My questions are:

Why does this not work? I can see that operator|= is not a constexpr, but does it matter for built-in types?

Is there an easy way to write this function as a constexpr? I would like it to be reasonable efficient at runtime, and I care a bit about readibility.

You cannot perform assignment in a constant expression and you cannot use the comma operator (I'm not 100% sure about the comma operator; you certainly couldn't use it in C++03). All you have to do is rewrite this so it doesn't use those two operators. It should be straightforward using recursion. — James McNellis
– James McNellis, Commented Jul 23, 2011 at 15:25
Thanks fot the quick answer. the comma operator seems to be accepted by g++ 4.6.1 at least. I was not aware of forbidden assignment, and at first sight, it seems to make constexpr a lot less neat. — mirk
– mirk, Commented Jul 23, 2011 at 15:39
@DirkM: constexpr seems really neat, until you learn about all the restrictions. — Puppy
– Puppy, Commented Jul 23, 2011 at 15:41

kennytm · Accepted Answer · 2011-07-23 16:01:58Z

8

(Not tested on GCC because I don't have 4.6, but I've verified that the algorithm is correct.)

To use constexpr you must not have assignments. Therefore, you often have to write in functional form with recursion:

#include <cstdint>
#include <climits>

constexpr inline uint64_t highestBit(uint64_t p, int n = 1) {
    return n < sizeof(p)*CHAR_BIT ? highestBit(p | p >> n, n * 2) : p - (p >> 1);
}

int main() {
    static_assert(highestBit(7) == 4);
    static_assert(highestBit(5) == 4);
    static_assert(highestBit(0x381283) == 0x200000);
    return 0;
}

You can check C++0x §[expr.const]/2 to see what expressions cannot be used in a constexpr function. In particular, the second to last item is "an assignment or a compound assignment".

edited Jul 23, 2011 at 16:01

answered Jul 23, 2011 at 15:55

kennytm

526k110 gold badges1.1k silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

mirk Over a year ago

That was insightful. I was hoping to get away from recursive tmeplate instantiations. It seems that I will have to learn to live with recursive constexpressions.

Vitus Over a year ago

@DrikM: There are no templates involved, it's just plain recursion.

mirk Over a year ago

@Vitus: the original code (not published here) used templates to do the same as the constexpr here. (My comment was not very clear without context).

Ben Voigt · Accepted Answer · 2011-07-23 16:07:08Z

3

constexpr inline uint64_t highestBit(uint64_t p)
{
    return (p & (p-1))? highestBit(p & (p-1)): p;
}

Each level of recursion clears the rightmost bit that was set, when the final bit would be cleared, only the highest bit remained, so it's returned.

edited Jul 23, 2011 at 16:07

answered Jul 23, 2011 at 16:02

Ben Voigt

286k45 gold badges444 silver badges764 bronze badges

2 Comments

mirk Over a year ago

Thanks, I picked the other answer because the worst-case recursion is less deep there, and the compiler could theoretically unroll it. (although, I will have to look closer at my usecase).

Ben Voigt Over a year ago

@DirkM: The compiler should unroll either one at compile time. But when the argument isn't a constant, yes this one could involve more recursion (although, the compiler may still transform it to iteration with no additional function calls).

Collectives™ on Stack Overflow

constexpr with operator|=

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related