How to fast set 9 bits after all '1's in an 64 bit integer

Question

I am writing a C++ program and require a function that sets all 9 bits to 1 after all existing '1's.

That is, I'm going to write a function void set10BitsFull(int64_t& n) that for an integer "int64_t n = 0b...1000000000...", set10BitsFull(n) transforms n to "0b...1111111111...".

(Update) Bits of the input integer are sparsely set to 1, and there are at least 10 bits distance between two 1. For an sample input 0x20000200, the expected output is 0x3FF003FF. There will be at least 9 bits 0 after the last 1. The leftmost 10 bits will always be zero.

Here is my implementation of this function

/**
 * Inline function that set 10 bits to 1 after each set 1
 * i.e.,
 * ......1000000000...... -> ......1111111111.......
 *
 * @param n
 *      pointer of input number
 */
inline void set10BitFull(int_fast64_t *n) {
    // n = 1000000000
    *n |= (*n >> 1); // n = 1100000000
    *n |= (*n >> 2) | (*n >> 4) | (*n >> 6) | (*n >> 8); // n = 1111111111
}

In main loop of the program these two lines of code will be frequently called, and in previous testing, the computation cost is extremely high. Hence I would like to seek an approach that takes less computation overhead (less cpu cycles to compute), and possible solutions might include:

• Use precomputed masks
• Inline assembly
• x86/gcc builtin intrinsic ...

Answer 1

You could do something like :

constexpr uint_fast64_t set10BitFull(uint_fast64_t n) {
    return (n << 1) - (n >> 9);
}

That should work with all inputs you described, where there are at least 9 0 bits after every 1 bit.