Set the leading zero bits in any size integer C++

Question

I want to set the leading zero bits in any size integer to 1 in standard C++.

eg.

0001 0011 0101 1111 -> 1111 0011 0101 1111

All the algorithms I've found to do this require a rather expensive leading zero count. However, it's odd. There are very fast and easy ways to do other types of bit manipulation such as:

 int y = -x & x; //Extracts lowest set bit, 1110 0101 -> 0000 0001

 int y = (x + 1) & x; //Will clear the trailing ones, 1110 0101 - > 1110 0100

 int y = (x - 1) | x; //Will set the trailing zeros, 0110 0100 - > 0110 0111

So that makes me think there must be a way to set the leading zeros of an integer in one simple line of code consisting of basic bit wise operators. Please tell me there's hope because right now I'm settling for reversing the order of the bits in my integer and then using the fast way of setting trailing zeros and then reversing the integer again to get my leading zeros set to ones. Which is actually significantly faster than using a leading zero count, however still quite slow compared with the other algorithms above.

 template<typename T>
 inline constexpr void reverse(T& x)
 {
    T rev = 0;
    size_t s = sizeof(T) * CHAR_BIT;

    while(s > 0)
    {
        rev = (rev << 1) | (x & 0x01);
        x >>= 1;
        s -= 1uz;
    }//End while

    x = rev;
 }

 
 template<typename T>
 inline constexpr void set_leading_zeros(T& x)
 {

     reverse(x);

     x = (x - 1) | x;//Set trailing 0s to 1s
     
     reverse(x);
 }

Edit

Because some asked: I'm working with MS-DOS running on CPUs ranging from early X86 to a 486DX installed in older CNC machines. Fun times. :D

Answer 1

The leading zeroes can be set without counting them, while also avoiding reversing the integer. For convenience I won't do it for a generic integer type T, but likely it can be adapted, or you could use template specialization.

First calculate the mask of all the bits that aren't the leading zeroes, by "spreading" the bits downwards:

uint64_t m = x | (x >> 1);
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
m |= m >> 32;

Then set all the bits that that mask doesn't cover:

return x | ~m;

Bonus: this automatically works even when x = 0 and when x has all bits set, one of which in a count-leading-zero approach could lead to an overly large shift amount (which one depends on the details, but almost always one of them is troublesome, since there are 65 distinct cases but only 64 valid shift amounts, if we're talking about uint64_t).